1. Introduction

One very popular procedure in combinatorial group theory is due to Todd and Coxeter and systematically enumerates all cosets of a finitely generated subgroup in a given finitely presented group [26]. Nielsen reduced sets allow the computation of Schreier coset representatives hence enabling syntactical solutions to the subgroup problem in finitely generated free groups [22]. Another approach to the study of groups stems from the fact that they can be presented as string rewriting systems and, hence, completion based procedures a la Knuth and Bendix can be applied [12]. Recently, some authors have started using Gröbner basis methods to model groups in appropriate rings and solve group theoretical problems in this setting [17,4].

In [17] the existence of explicit connections between the word problem for monoids and groups and the ideal membership problem in free monoid and free group rings, respectively, as well as connections between the submonoid problem and the subalgebra problem and between the subgroup problem and the one-sided ideal membership problem is proven. These results strongly encourage people designing new algorithms for attacking monoid or group theoretical problems to look for methods in all three fields mentioned above. Here we want to present the fundamental results of Nielsen and Todd and Coxeter from combinatorial group theory using Gröbner basis techniques for free group rings. More on connections between the Todd-Coxeter coset enumeration procedure (abbreviated by TC in the following) and the Knuth-Bendix completion procedure (abbreviated by KB) for the special case of the trivial subgroup can be found in [2,25].

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
.
In 1911 Dehn stated decision problems for groups, two of which will be studied here
using coset enumeration:
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 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 these two problems in the case of arbitrary finitely presented groups
is 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 multiplication
table of the cosets.
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 (compare [3]).
The most important procedure is due to Knuth and Bendix and allows computing convergent^{2}
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. [3] and [13].
The presentation of a finitely generated free group in terms of the inverse relators can be interpreted as
a convergent string rewriting system and free reduction is exactly reduction using this string rewriting system.
In [2] it is outlined how TC and KB are related for the special
case of the *trivial* subgroup:
for a modified version of TC, which represents the cosets by appropriate words on
and uses a certain strategy (depending on the ordering chosen for the
words representing the elements of the group) 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 TC.
What now are the essential differences between TC and KB in this case?
In case TC terminates so will a specialized version of KB but the converse does not hold.
This is due to the fact that TC, when viewed as a rewriting procedure, does
not apply ordinary string rewriting but *prefix rewriting*.
Now if no finite convergent system with respect to
prefix rewriting exists, TC does not detect whether it might already have computed a convergent set of rules
with respect to ordinary string rewriting and hence will not terminate although KB might.
Variants of prefix rewriting have a long tradition when studying subgroups using
string rewriting techniques (compare [13]).
But there are two main differences:
These techniques require certain assumptions for the relators defining the group
(e.g. convergence) while TC allows any presentation.
The output gained by prefix string rewriting completion techniques 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 prefix string rewriting techniques can also handle cases where the
subgroup has infinite index.
A well-known algorithm can be found for free groups: In a finitely presented free group
the subgroup problem can be solved using Nielsen reduced sets of generators and
prefix string rewriting.

KB techniques can be applied to complete group presentations as string rewriting systems.
Sims incorporated prefix string rewriting techniques for the subgroup generators by decoding
them as special rules of the form
where $ is a new symbol.
In [25] he compares running KB on input
where *R* are the relators and *U* the subgroup generators to TC.
However, in general the completion does not terminate even for subgroups of finite index.
This is due to the fact that
it will always compute a convergent presentation for the group which need not be finite.
In Section 5 we will outline how our procedure using Gröbner basis techniques
can be ``translated'' into a Knuth-Bendix type procedure which simulates TC *and*
always terminates if the subgroup has finite index.

In this paper we present TC in an unusual framework
due to the fact that monoids and groups can be simulated by binomial ideals^{3} in free monoid
and free group rings.
A first explicit connection between finitely presented *commutative* monoids
and ideals in *commutative* polynomial rings was
used 1958 by Emelichev
yielding a solution to the word problem in the monoid by
deciding the ideal membership problem (compare [18]):
Assuming the commutative monoid
is presented by a set of
generators
and a set of defining relations
the following is true:
A relation *u*=*w* holds in
if and only if the polynomial
*u*-*w* lies in the ideal generated by the polynomials
in the polynomial ring
.
In his paper Emelichev uses the result of Hermann presented in [9] to show that the
latter question is decidable.
Of course the ideal membership problem is also solvable using Buchberger's
method of Gröbner bases, which is based on a special reduction
system associated to finite sets of polynomials which represent ideal
congruences in polynomial rings [6].

It was observed independently in [20,23,17] that similar results hold for congruences on arbitrary finitely generated monoids and groups. Here we want to develop these ideas for the free group case in order to give a coset enumerating procedure using Gröbner techniques for free group rings:

Let
denote the free group generated by
.
The elements of
are represented by the freely reduced words in
and multiplication of two elements, denoted by ,
is just their concatenation followed by free reduction.
In the following we will not distinguish between group elements and their representation.
The empty word
represents the unit in
.
By
we denote the **free group ring**, i.e. the set of finite formal sums
,
,
where
denotes
multiplication with scalars and
will denote multiplication in
.
The elements are called polynomials.
The precedence
induces a length lexicographical ordering on
denoted by
which is well-founded and total,
but unfortunately not admissible for
^{4}.
This ordering can be lifted to
and used to
distinguish the **head term**
,
**head
coefficient**
and **head monomial**
of a polynomial *f* and
for subsets *F* of
as usual.
Identifying the elements of
by their representatives we define
the syntactically motivated concept of prefix reduction:
For two non-zero polynomials *p*, *f* in
,
we say *f* **prefix reduces**
*p* to *q* at a monomial
,
,
of *p* in one step, denoted by
,
if
is a prefix of *t* as a word (i.e.
for some
where
stands for the concatenation of
and *w* and
denotes identity as words) and
.
We will call a basis *G* of a right ideal
in
a **prefix Gröbner basis** of
,
if
.
*G* is called **reduced** if no polynomial in *G* is prefix reducible
by another polynomial in *G*.
As in the commutative case congruences on the free group
are modeled using
special polynomials:
A subset of the free group ring
is called a
binomial basis of an ideal
,
if
it consists solely of polynomials of the form *u* - *v*
where
and *u* > *v*^{5}.
We will speak of **binomial ideals** in case they have a binomial basis.
Such ideals are strongly related to the word problem in groups (compare [23,17])
and hence are the appropriate connection to TC.
The FGLM algorithm^{6}
(see [7,8,19])
was introduced as a tool to study the duality of ideals: the central procedure
MATPHI enumerates as a bonus the set *N* (called the *natural basis* of *G* there)
of terms which are irreducible by
the Gröbner basis and a table for
the multiplication of elements in *N* by variables.
Therefore, by combining a generalization of
the MATPHI algorithm presented in [8] and prefix Gröbner bases [15,16]
we produce a coset enumeration procedure which is a verbatim
interpretation of TC.
An implementation of the procedure was done in MRC (a system for computing Gröbner bases in monoid
and group rings developed at the University of Kaiserslautern).

The paper is organized as follows: In Section 2 we present the basics on Nielsen reduction and TC. Section 3 summarizes the necessary results from Gröbner basis theory which are applied in Section 4 to give a coset enumeration procedure based on prefix Gröbner bases in free group rings. Section 5 summarizes our results and points out how our procedure can be transformed into a Knuth-Bendix type completion procedure directly comparable to TC.