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. ).
Subgroups of groups can be characterized by one-sided congruences on the
In the following we restrict ourselves to the case of right congruences (left congruences can be
introduced in a similar fashion).
be a subgroup of a group .
we can define
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.