Next: 4. The Todd-Coxeter Coset Up: Observations on Coset Enumeration Previous: 2. String Rewriting Methods

# 3. The Subgroup Problem

This section outlines the subgroup problem for groups and its connections to string rewriting techniques.

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

For a finite subset S of a group and 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 . We say a group has solvable generalized word problem if for every finite subset S of the subgroup problem for is decidable.

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.

Next: 4. The Todd-Coxeter Coset Up: Observations on Coset Enumeration Previous: 2. String Rewriting Methods
| ZCA Home | Reports |