1. Introduction

A group ${\cal G}$ is called finitely presented if there is a finite set of generators $\Sigma$ and a finite set of relators R such that ${\cal G}$ is isomorphic to the quotient of the free group generated by $\Sigma$ modulo the congruence generated by R. Let $\bar{\Sigma} = \Sigma \cup \Sigma^{-1}$ where $\Sigma^{-1} = \{a^{-1} \mid a \in \Sigma \}$ denotes the set of formal inverses for the generators. The group elements then are represented as words on $\bar{\Sigma}$ with the empty word $\lambda$ representing the one.

In 1911 Dehn stated decision problems for groups: The word problem for a group is to decide whether two representations describe the same group element. The subgroup problem for a group is to decide for a group element and a finitely generated subgroup of the group whether the element is in fact a member of the subgroup.

Both problems are undecidable in general, but become decidable when restricted to special classes of groups. For finitely generated free groups the word problem can be solved by free reduction, i.e. by deleting occurrences of subwords of the form aa^-1 and a^-1a for $a \in \Sigma$. The subgroup problem can be solved using Nielsen reduced sets due to the fact that there is a lot of crucial information on the maximal parts of words which can cancel each other when multiplying generating elements of subgroups. A well established procedure for dealing with both problems in the case of arbitrary finitely presented groups is the Todd-Coxeter coset enumeration method (TC): Given a set of defining relators for the group ${\cal G}$ and a set of generators of the subgroup ${\cal H}$ (as words in the generators of ${\cal G}$) TC enumerates the cosets of ${\cal H}$ in ${\cal G}$. Of course this process can only stop in case ${\cal H}$ has finite index in ${\cal G}$ and then TC also provides the coset table, i.e. all multiples of cosets by generators. Now given a word w in the generators of ${\cal G}$ we have that $w \in {\cal H}$ if and only if w is in the coset of the identity. Hence TC provides a semi-decision procedure by determining, while enumerating cosets, whether w is in one of the cosets enumerated so far, and answering ``yes'' in case it is in the coset of the identity. It is obvious that the answer ``no'' can only be given in case the procedure terminates, since as long as more cosets are enumerated there is the possibility of cosets collapsing, i.e., even if w is found in a coset which is not the identity it might later on be derived that the coset coincides with the coset of the identity. Notice that when choosing the trivial group as the subgroup ${\cal H}$, TC in fact enumerates all elements of the group ${\cal G}$ and terminates if and only if ${\cal G}$ is finite.

Group presentations can be interpreted as string rewriting systems and this field is well studied. Its most important procedure is due to Knuth and Bendix and allows computing convergent¹ presentations for groups. In case such a presentation is additionally finite it can be used to compute unique normal forms for the group elements and hence to decide the word problem for the group. The advantage is that this method is often still applicable to infinite groups. For an overview see e.g. [2] and [5].

The presentation of a finitely generated free group in terms of the trivial relators can be interpreted as a convergent string rewriting system and free reduction is exactly reduction using this string rewriting system.

In [1] it is outlined how TC and KB are related for the special case of the trivial subgroup, i.e. for finite groups: A modified version of TC is presented, which represents the cosets by appropriate words on $\bar{\Sigma}$ and uses a certain strategy to replace cosets when new equations are obtained. On termination the output of KB is a subset of the rules corresponding to the equations generated by the modified version of TC. What now are the essential differences between TC and KB in this case? If TC terminates so will a specialized version of KB but the converse does not hold. This difference in behaviour is due to the fact that TC, when viewed as a rewriting procedure, does not apply ordinary string rewriting but prefix string rewriting². Now in case the index is not finite, TC will not terminate although the set of rules corresponding to the equations generated by TC so far might include a finite convergent presentation of the group.

In [9] a similar idea is applied to finite monoids: Given a string rewriting system, the procedure terminates if and only if the monoid is finite and then yields the multiplication table of the monoid.

Variants of prefix rewriting have a long tradition when studying subgroups using string rewriting techniques. However, there are two main differences in these approaches: While Kuhn et. al. [4,5] require the group to have a convergent presentation, Sims [15] like TC allows any presentation. The output gained by the prefix string rewriting completion techniques in [4,5] is a description of cosets of the subgroup in the group while TC enumerates cosets of the subgroup generated by the original subgroup generators and the normal closure of the relators in the corresponding free group. This difference explains why the former prefix approach can also handle cases where the subgroup has infinite index, but a ``nice'' finite description for the cosets can be found, e.g. by an automaton. For a convergent group presentation Sims' approach [15] is equivalent to the one by Kuhn et. al. [4,5]. Else it additionally computes a convergent presentation for the group and hence, contrary to TC, will not always terminate for finite index. For the special case where the group completion diverges while the index is finite, additional knowledge has to be used to determine that the completion process can be stopped (see Section 3.10 in [15] for more details). We overcome this problem by translating the algebraic characterization of TC as presented by Reinert, Mora and Madlener in [14] into a prefix string rewriting procedure which can be generalized to the case of monoids.

The paper is organized as follows: First we give short introductions to string rewriting theory, the subgroup problem and the Todd-Coxeter coset enumeration method. Then in Section 5 we outline the approach of Kuhn and Madlener for studying the subgroup problem using prefix string rewriting methods and its connections to TC by giving an example. In Section 6 we sketch Sims' simulation of prefix string rewriting using ordinary string rewriting and compare his results for the subgroup problem to the ones by Kuhn and Madlener, and TC. Additional knowledge has to be incorporated into the completion procedure to make it terminating for all finite index situations. In Section 7 we give a procedure where this is no longer necessary. Finally in Section 8 we generalize this procedure to free monoids and give an algebraic characterization of the structure it computes. It turns out that we exactly get the ``blocks'' described by Neumann in [12] as a generalization for cosets of submonoids in monoids. These results can be compared to the more general work of Labonté [6] and Linton [7].

Acknowledgments. The author thanks Klaus Madlener, Teo Mora and Steve Linton for valuable discussions on some ideas of this paper.