Next: 6. Relating the Submonoid Up: Relating Rewriting Techniques on Previous: 4. Relating the Word

# 5. Relating the Generalized Word and One-Sided Ideal Membership Problems in Groups and Group Rings

This section is concerned with another fundamental decision problem introduced by Dehn in 1911 for groups.

Definition 8   Given a subgroup of a group the generalized word problem for or the subgroup problem for is to determine, given , whether .

Given a finite subset S of a group , we let denote the subgroup generated by S. A subgroup of a group is called finitely generated if there exists a finite subset S of such that .

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. [Mi91]).

Now due to the existence of inverses, the word problem for congruences on free groups can also be formulated as a special type of subgroup problem. Let T be a set of relations on a free group . Then we can associate a set to T by setting . Let be the normal closure6 of T1 in . Then in fact the word problem for the group can be reduced to the subgroup problem for since a relation u=v holds in if and only if holds in , i.e.  . Notice that in general is not a finitely generated subgroup.

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 induced by on . The subgroup itself is a congruence class, namely the one generated by . This right congruence is a congruence if and only if is a normal subgroup.

The fact that holds if and only if , is used in the proof of the next theorem, which states that the subgroup problem for a group is equivalent to a special instance of the right respectively left ideal membership problem in the corresponding group ring.

Theorem 9 ([Re95,MaRe93])   Let S be a finite subset of and the group ring over . Further let be the set of polynomials associated to S. Then the following statements are equivalent:
(1)
.
(2)
.
(3)
.

Proof : 1.11.1

Next: 6. Relating the Submonoid Up: Relating Rewriting Techniques on Previous: 4. Relating the Word
| ZCA Home | Reports |