The method of Gröbner bases allows to solve many problems related to
polynomial ideals in a computational fashion.
It was shown by Hilbert (compare Hilbert's basis theorem) that every
ideal in a polynomial ring has a finite generating set.
However, an arbitrary finite generating set need not provide much
insight into the nature of the ideal.
Let
*f*_{1} = *X*_{1}^{2} + *X*_{2} and
*f*_{2} = *X*_{1}^{2} + *X*_{3} be two polynomials
in the polynomial ring^{3}
.
Then
is the ideal they generate
and it is not hard to see that
the polynomial *X*_{2} - *X*_{3} belongs to
since
*X*_{2} - *X*_{3} =
*f*_{1} - *f*_{2}.
But what can be said about the polynomial
*f* = *X*_{3}^{3} + *X*_{1} + *X*_{3}?
Does it belong to
or not?

The problem to decide whether a given polynomial lies in a given ideal is called the membership problem for ideals. In case the generating set is a Gröbner basis this problem becomes immediately solvable, as the membership problem then reduces to checking whether the polynomial reduces to zero.

In our example the set
is a
generating set of
which is in fact a Gröbner basis.
Now returning to the polynomial
*f* = *X*_{3}^{3} + *X*_{1} + *X*_{3} we find that
it cannot
belong to
since neither *X*_{1}^{2} nor *X*_{2} is a divisor
of a term in *f* and hence *f* cannot be reduced to zero by the
polynomials in the Gröbner basis.

Further applications of Gröbner bases to algebraic questions can be found e.g. in the work of Buchberger [Bu87], Becker and Weispfenning [BeWe92] and in the book of Cox, Little and O'Shea [CoLiOS92].

In the last years, the method of Gröbner bases and its applications have been extended from commutative polynomial rings over fields to various types of non-commutative algebras over fields and other rings. In general for such rings arbitrary finitely generated ideals will not have finite Gröbner bases. Nevertheless, there are interesting classes for which every finitely generated (left or right) ideal has a finite Gröbner basis which can be computed by appropriate variants of Buchberger's algorithm.

First successful generalizations were extensions to commutative polynomial rings over coefficient domains other than fields. It was shown by several authors including Buchberger, Kandri-Rody, Kapur, Narendran, Lauer, Stifter and Weispfenning that Buchberger's approach remains valid for polynomial rings over the integers, or even Euclidean rings, and over regular rings (see e.g. [Bu83,Bu85,KaKa84,KaKa88,KaNa85a,La76,St85,We87]). For regular rings Weispfenning has to deal with the situation that zero-divisors in the coefficient domain have to be considered.

Since the development of computer algebra systems for commutative algebras enabled to perform tedious calculations using computers, attempts to generalize such systems and especially Buchberger's ideas to non-commutative algebras followed. Originating from special problems in physics, Lassner in [La85] suggested how to extend existing computer algebra systems in order to handle special classes of non-commutative algebras, e.g. Weyl algebras. He studied structures where the elements could be represented using the usual representation of polynomials in commutative variables and the non-commutative multiplication could be performed by a so-called ``twisted product'' which required only procedures involving commutative algebra operations and differentiation. Later on together with Apel he extended Buchberger's algorithm to enveloping fields of Lie algebras [ApLa88]. Because these ideas use representations by commutative polynomials, Dickson's lemma can be carried over. The existence and construction of finite Gröbner bases for finitely generated left ideals is ensured. In [Ga88] Galligo also studied algorithmic questions on ideals of differential operators.

On the other hand, Mora gave a concept of Gröbner bases for a class of non-commutative algebras by saving an other property of the polynomial ring while losing the validity of Dickson's lemma. The usual polynomial ring can be viewed as a monoid ring where the monoid is a finitely generated free commutative monoid. Mora studied the class where the free commutative monoid is substituted by a free monoid - the class of finitely generated free monoid rings (compare e.g. [Mo85,Mo94]). The ring operations are mainly performed in the coefficient domain while the terms are treated like words, i.e., the variables no longer commute with each other. The definitions of (one- and two-sided) ideals, reduction and Gröbner bases are carried over from the commutative case to establish a similar theory of Gröbner bases in ``free non-commutative polynomial rings over fields''. But these rings are no longer Noetherian if they are generated by more than one variable. Mora presented a terminating completion procedure for finitely generated one-sided ideals and an enumeration procedure for finitely generated two-sided ideals with respect to some term ordering in free monoid rings.

Gröbner bases and Mora's Algorithm have been generalized to path algebras (see [FaFeGr93,Ke97]); free non-commutative polynomial rings are in fact a particular instance of path algebras.

Another class of non-commutative rings where the elements can
be represented by the usual polynomials and which allow the construction of finite
Gröbner bases for arbitrary ideals are the so-called solvable rings, a class
intermediate between commutative and general non-commutative
polynomial rings.
They were studied by Kandri-Rody, Weispfenning and Kredel [KaWe90,Kr93].
Solvable polynomial rings can be described by ordinary polynomial
rings
provided with a ``new'' definition of multiplication which coincides with the
ordinary multiplication except for the case that a variable *X*_{j} is
multiplied with a variable *X*_{i} with lower index, i.e., *i*<*j*.
In the latter case multiplication can be defined by equations of the form
where
and *p*_{ij} is a polynomial
``smaller'' than *X*_{i}*X*_{j} with respect to a fixed admissible term
ordering on the polynomial ring.

The more special case of twisted semi-group rings, where
*c*_{ij} = 0
is possible, has been studied in [Ap88,Mo88].

In [We92] Weispfenning showed the existence of finite Gröbner
bases for arbitrary finitely
generated ideals in non-Noetherian skew polynomial rings over two
variables *X*,*Y* where a ``new'' multiplication
is introduced
such that
and
for some fixed
.

Ore extensions have been successfully studied by Pesch in his PhD Thesis and his results on two-sided Gröbner bases are presented in this volume [Pe97].

Most of the results cited so far assume admissible well-founded orderings on the set of terms so that in fact reduction can be defined by considering the head monomials only.
This is essential to characterize Gröbner bases in the
respective ring with respect to the corresponding reduction in a
finitary manner and to enable to decide whether a finite set is a Gröbner
basis by checking whether the s-polynomials are reducible to
zero^{4}.

There are rings combined with reduction where admissible well-founded orderings cannot
be accomplished and, therefore, other concepts to characterize
Gröbner bases have been developed.
For example
in case the ring contains zero-divisors a well-founded ordering on the ring
is no
longer compatible with the ring multiplication^{5}.
This phenomenon has been studied for the case of zero-divisors in
the coefficient domain by Kapur and Madlener [KaMa86] and by
Weispfenning for the special case of regular rings [We87].
In his PhD thesis [Kr93], Kredel described problems occurring when
dropping the
axioms guaranteeing the existence
of admissible orderings in the theory of solvable polynomial rings by
allowing
*c*_{ij} = 0 in the defining equations above.
He sketched the idea of using saturation to repair some of them.
Saturation enlarges the generating sets in order to ensure that
enough head terms exist to do all necessary reductions and
this process can often be related to additional special critical pairs.
Similar ideas can be found in the PhD thesis of Apel [Ap88].
For special cases, e.g. for the Grassmann
(exterior) algebras, positive results can be achieved (compare the paper
of Stokes [St90]).

Before we move on to give a more abstract generalization of structures allowing Gröbner basis algorithms, let us first summarize some important notations and definitions of reduction relations and basic properties related to them, as can be found more explicitly for example in the work of Huet or Book and Otto ([Hu80,Hu81,BoOt93]).

Let
be a set of elements and
a binary relation on
called **reduction**.
For
we will write
in case
.
A pair
will be called a **reduction system**.
Obviously the reflexive symmetric transitive closure
is an equivalence
relation on
and the reflexive transitive closure
can be viewed as a
reduction relation on .

Well-known decision problems related to a reduction system are the word problem and the generalized word problem.

An element
is said to be **reducible**
(with respect to
)
if there
exists an element
such that
.
All elements
such that
are
called **successors**
of *a* and in case
they are called **proper successors**.
An element which has no proper successor is called
**irreducible**.
In case
and *b* is irreducible, *b* is called a
**normal form** of *a*.
Notice that for an element *a* in
there can be no,
one or many normal forms.

Then is confluent if and only if is locally confluent.

Besides the extensions of Buchberger's ideas using knowledge on the algebra mentioned before there are also considerations of finding essential properties of reduction for a ring to allow finite Gröbner bases - the idea of defining so-called reduction rings. A first generalization of this kind was given by Buchberger himself and his student Stifter in characterizing reduction rings by adding additional axioms to the ring axioms [St85,St87]. Another approach was given by Kapur and Narendran for polynomials over reduction rings in [KaNa85a].

We will here use the axiomatization given by Madlener in 1986: Let be a ring with a reduction associated with subsets satisfying the following axioms

- (A1)
- , is terminating for all subsets .
- (A2)
- implies .
- (A3)
- for all .

Further let
be the ideal generated by the set *B*
in .
If
denotes the congruence generated by ,
from (A1) and (A2)
follows.
One method for solving the membership problem for
by
reduction methods is to transform *B* into a finite set *B*' such that
is confluent on .
Notice that 0 has to be irreducible for all
,
.
Therefore, 0 will be chosen as the normal form of the ideal elements.
Hence the goal is to achieve
if and only if
.
In particular *B*' also generates
and
is one
equivalence class of
.
The different definitions of reductions in rings existing in literature show
that for solving the membership problem it is not necessary to enforce
.
E.g. the D-reduction notion given by Pan in [Pa85] does not
have this property but it suffices
to decide
-equivalence of two elements because
if and only if
.
It may happen that D-reduction is not only confluent on
but
confluent everywhere and still
does not
imply that the normal forms with respect to D-reduction are the same.

With this in mind there are several possible definitions of G-bases (Gröbner bases) when relating them to the solvability of the membership problem. We want to restrict ourselves to the original intention of Buchberger in which holds.

The notion of one-sided reduction rings can be defined similarly.

Also effective or computable reduction rings can be defined (e.g. Buchberger's reduction rings) namely those for which reduction is effective and there exists an algorithm for computing a finite G-basis from a finite set of generators of the ideal.

It is often useful, if satisfies an additional axiom strongly related to interreduction.

- (A4)
- and imply or .

In general we have to compute G-bases and syzygy bases for sets of elements in the original reduction ring in order to lift the G-bases computations to the new reduction ring. In case the original reduction ring is a principal ideal ring, only special sets, namely of size two for the G-bases and of size one for the syzygy bases, have to be considered.

That different choices of reduction are possible shall be illustrated in a short example. Let us consider the reduction ring for some . Then the polynomial ring again is a reduction ring. Reduction in on one hand can be defined by lifting the reduction given in (compare theorem 1.9). But we can also view as a quotient, namely , and lift a reduction defined for the polynomial ring to our structure (compare theorem 1.10). This shows that there are various ways to treat a given ring as a reduction ring by specifying different reductions.

Several fields where reduction systems are studied and used can be found in
computer science.
The theory of term rewriting systems plays an important role e.g. in
algebraic specifications of abstract data structures, equational programming,
program transformation or automated theorem proving.
The concept of completion based on the Knuth-Bendix
completion procedure given in [KnBe70]
has become very influential in this field.
In [LeCh86] Le Chenadec describes how with many equational
classes of algebras one can associate a completion procedure of
a finitely presented algebra *A* in the class which translates
a presentation of *A* into a (not necessarily finite) complete set
of syntactic replacement rules. He incorporates the ideas of rewriting
modulo theories (class rewriting) which can be generalized to normalized
rewriting [Mar93].
He also includes algorithms encoding knowledge about the input which
linearly solve the word problem for some classes of groups (e.g. small
cancellation groups introduced by Dehn [De12] where he presented
a string-rewriting based solution to the word problem for these groups).

Several authors have studied the relations between Buchberger's algorithm and the Knuth-Bendix completion procedure. The main difficulty is to capture fields, since they are not equationally definable. Hence by using conditional or more generally constraint rewriting this problem can be surpassed. In fact Bachmair and Ganzinger have shown that Buchberger's algorithm can be viewed as a constraint-based variant of completion [BaGa94b] where the operations in the coefficient field are expressed via constraints and separated from the computations in the polynomial ring structure done by rewriting. Earlier attempts using class rewriting can be found in [KaKaWi89]. Madlener and Reinert have shown that certain undecidability results for string rewriting systems carry over to monoid and group rings since the specialization of the Knuth-Bendix completion procedure for string rewriting systems is an instance of Mora's generalization of Buchberger's algorithm for free monoid rings [Re95]. These results can be found in the next section of this paper.

As we have seen there are two main approaches to use rewriting techniques for symbolic computation. One is to give a formal definition of the objects by means of axiomatization in a term rewriting system. The other is to solve problems in special structures by incorporating knowledge on the structure into the procedure. In this paper we want to show how this can be done for monoid and group rings by giving different notions of reduction and showing how specializing the reduction according to the given group presentation leads to algorithmic solutions for some classes of groups. Since our approach combines rewriting for the presentation of the monoid or group and polynomial rewriting in the field of monoid and group rings, let us first introduce a special kind of term rewriting systems, the so called string rewriting systems or semi-Thue systems. These systems are strongly related to the idea of presenting monoids or groups in terms of generators and defining relations [Gi79,LySch77,MaKaSo76].

A semi-Thue system consists of an alphabet
and a set of rules
^{7}.
We write
if and only if
and
for some
,
.
is the reflexive and transitive closure of
.
Every monoid
can be presented by a semi-Thue system
,
where
is an alphabet and *T* a set of rules.
One only has to choose
and *T* the multiplication table
of the monoid, but this presentation might be infinite or even non-recursive.
There have been numerous studies investigating special kinds of semi-Thue
presentations and the influence of certain properties on the decidability
of certain questions related to the monoid or group they present.
Of special interest is the question which monoids have presentations by
finite convergent semi-Thue systems and how to compute them.
Kapur and Narendran in [KaNa85b] and Jantzen in [Ja81,Ja85] give
examples of monoid presentations for which completion does not terminate
(i.e. there is no equivalent finite convergent system with respect to
any completion ordering) although
a finite convergent semi-Thue system over a different alphabet presenting
the same monoid exists.
Squier proved the existence of finitely presented monoids with decidable
word problem which cannot be presented by a finite convergent semi-Thue
system [Sq87].
In [De92] Deiß introduces conditional semi-Thue systems and gives
finite convergent conditional presentations for the monoids given by Narendran and Squier.

Besides demanding overall confluence, to decide the word problem for a group confluence on the congruence class of is sufficient. The property of being confluent on specific congruence classes only and specialized completion procedures for such presentations have been studied by Otto and others [Ot87,OtZh91,MNOZ93].

The subgroup problem is also an important decision problem for groups. Kuhn and Madlener have shown how the notion of prefix rewriting - a specialization of ordinary string rewriting - can be applied to solve the subgroup problem for certain classes of groups [KuMa89]. Prefix rewriting and its completion is a direct generalization of Nielsen's method to solve the subgroup problem in the class of free groups [Ni21]. In case of confluence it can be used to compute Schreier-representatives of the subgroup cosets. A related question is when subgroups of groups allowing certain presentations again have a presentation of the same type. For some groups such a presentation for the subgroup can be computed from a confluent prefix rewriting system for the subgroup [KuMaOt94].

We will restrict ourselves to presentations of monoids and groups,
where
is finite and *T* is finite, confluent and Noetherian,
i.e., each word in
has a unique normal form with respect to *T*.
Furthermore, we require the existence of a total, well-founded ordering
which is admissible^{8} on
such that
for all
,
holds.
This ordering is called a completion ordering of
.
The monoid
is isomorphic to the set
of words
irreducible with respect to *T*.
The empty word
presents the identity of .
The word problem is solvable, which is essential for computation in
.
Multiplication of two terms
is defined by
.
The completion ordering of the presentation induces an ordering
on
such that
for
we get
and
.

The elements of a monoid ring
over a field
can
be presented as ``polynomials''
where only finitely many coefficients are non-zero.
Addition and multiplication
for two polynomials
and
is defined as
and
with
.
For a subset *F* of
we call the set
the **right ideal** and
the **two-sided ideal**
generated by *F*.
We will henceforth always assume that the field
is computable.

The contents of the remaining sections of the paper is an extension of
our work on Gröbner bases in arbitrary monoid rings as it was
presented at the ISSAC meeting in Kiew in 1993 [MaRe93b]
combined with some results of the PhD thesis [Re95].
It organizes as follows:
In section 2 some undecidability
results on the existence of finite Gröbner bases are presented.
Section 3 outlines our approach of introducing
reduction to a monoid ring
.
Two possible definitions of reduction - strong and prefix reduction -
are studied and characterizations of
Gröbner bases for finitely generated right ideals in the respective
settings are given.
A procedure which enumerates prefix Gröbner bases for finitely
generated right ideals is given.
We close the section by extending the characterization of prefix
Gröbner bases to two-sided ideals.
Finally, in section 4 we
prove termination of the procedure to compute prefix Gröbner bases
given in section 3 for some classes of groups,
namely finite, free and
plain groups, and show how this procedure can be extended to compute
finite prefix Gröbner bases in the class of context-free groups.
Section 5 gives some perspectives for further
work in this field.

**Addendum**

We want to point out that the approach given here has also been
specialized for the class of polycyclic groups [Re96,MaRe97a].
These results are outlined in the concluding remarks.
There we also present a table which illustrates how the existence of finite
Gröbner bases with respect to special reductions
is related to groups having a subgroup problem solvable by rewriting methods.

**Acknowledgments**

The first author wants to thank several colleagues for fruitful discussions.
In particular Bruno
Buchberger who introduced him to the study of reduction rings and Deepak
Kapur for sharing with him ideas all the years after the workshop held in Otzenhausen.
We both thank Andrea Sattler-Klein, Teo Mora, Paliath Narendran and Friedrich Otto for
valuable discussions on parts of this paper.
Volker Weispfenning has taken influence on parts of this work as the second
advisor of Reinert's PhD thesis [Re95].