1. Introduction

A group
is called **finitely presented** if there is a finite set
of **generators**
and a finite set of **relators** *R* such that
is isomorphic to the quotient of the free group generated by
modulo the congruence generated by *R*.
Let
where
denotes the set
of formal inverses for the generators.
The group elements then are represented as words on
with the empty word
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*^{-1}*a* for
.
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
and a
set of generators of the subgroup
(as words in the generators of
)
TC enumerates the cosets of
in .
Of course this process can only stop in case
has finite
index in
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
we have that
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 ,
TC in fact
enumerates all elements of the group
and terminates if and only if
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^{1}
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
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*^{2}.
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.