3. The Subgroup Problem

The word problem for a group
is just the generalized word problem
for the trivial subgroup in
since *u* = *v* holds in
if and only if
holds in ,
i.e.
.
Thus the existence of a group with undecidable word problem yields
undecidability for the generalized word problem for this group as well.
On the other hand, decidable word problem for a group does not
imply decidable generalized word problem (for an overview on
various decision problems for groups
see e.g. [10]).

Subgroups of groups can be characterized by one-sided congruences on the
group.
In the following we restrict ourselves to the case of right congruences (left congruences can be
introduced in a similar fashion).
Let
be a subgroup of a group .
Then for
we can define

where . It is easy to prove that is a right congruence. The subgroup itself is the congruence class of . This right congruence is a congruence if and only if is a normal subgroup.

Let us take a look at how the right congruence of the subgroup
generated by *S*
in the group
presented by
can be
described using string rewriting techniques.
To *S* we associate the set of rules
.
We study the rewriting relation induced by the combined reduction relation
which presents the right congruence
in that
.
Since we have
if and only if
,
this problem
becomes immediately solvable for appropriate reduction relations, e.g. in the case of
-confluence for
.
Following a short presentation of TC,
three different string rewriting approaches will be outlined and their output
compared to TC.