1. Introduction

One of the amazing features of computers is the ability to discover new mathematical results due to extensive computations impossible to be done by hand. Besides incredible numerical calculations, symbolical mathematical manipulations are substantial to many fields in mathematics and physics. Hence the idea of using a computer to do such manipulations led to open up whole new areas of mathematics and computer science. One important contribution to the field of computer algebra is Buchberger's algorithm for manipulating systems of polynomial equations. In 1965 Buchberger introduced the theory of Gröbner bases¹ for polynomial ideals in commutative polynomial rings over fields [Bu65]. It established a rewriting approach to the theory of polynomial ideals. Polynomials can be used as rules by giving an admissible² ordering on the terms and using the largest monomial according to this ordering as a left hand side of a rule. ``Reduction'' as defined by Buchberger then can be compared to division of one polynomial by a set of finitely many polynomials. A Gröbner basis G is a set of polynomials such that every polynomial in the polynomial ring has a unique normal form with respect to reduction using the polynomials in G as rules (especially the polynomials in the ideal generated by G reduce to zero using G). Buchberger developed a terminating procedure to transform a finite generating set of a polynomial ideal into a finite Gröbner basis of the same ideal.

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₁ = X₁² + X₂ and f₂ = X₁² + X₃ be two polynomials in the polynomial ring³ ${\bf Q}[X_1,X_2,X_3]$. Then $\imath = \{ f_1 \ast g_1 + f_2 \ast g_2 \mid g_1, g_2 \in {\bf Q}[X_1,X_2,X_3] \}$ is the ideal they generate and it is not hard to see that the polynomial X₂ - X₃ belongs to $\imath$ since X₂ - X₃ = f₁ - f₂. But what can be said about the polynomial f = X₃³ + X₁ + X₃? Does it belong to $\imath$ 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 $\{ X_1^{2} + X_3, X_2 - X_3 \}$ is a generating set of $\imath$ which is in fact a Gröbner basis. Now returning to the polynomial f = X₃³ + X₁ + X₃ we find that it cannot belong to $\imath$ since neither X₁² nor X₂ 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 ${\bf K}[X_1, \ldots, X_n]$ provided with a ``new'' definition of multiplication which coincides with the ordinary multiplication except for the case that a variable X<sub>j</sub> is multiplied with a variable X<sub>i</sub> with lower index, i.e., i<j. In the latter case multiplication can be defined by equations of the form $X_j \star X_i = c_{ij} X_iX_j + p_{ij}$ where $c_{ij} \in {\bf K}^*= {\bf K}\backslash \{ 0 \}$ and p<sub>ij</sub> is a polynomial ``smaller'' than X_iX_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 $\star$ is introduced such that $X \star Y = XY$ and $Y \star X = X^eY$ for some fixed $e \in {\bf N}^+$.

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⁴.

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⁵. 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 ${\cal E}$ be a set of elements and $\longrightarrow$ a binary relation on ${\cal E}$ called reduction. For $a,b \in {\cal E}$ we will write $a \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ in case $(a,b) \in\;\; \longrightarrow$. A pair $({\cal E},\longrightarrow)$ will be called a reduction system. Obviously the reflexive symmetric transitive closure $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ }$ is an equivalence relation on ${\cal E}$ and the reflexive transitive closure $\mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ }$ can be viewed as a reduction relation on ${\cal E}$.

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

Definition 1..1   The   word problem for $({\cal E},\longrightarrow)$ is to decide for $a,b \in {\cal E}$, whether $a \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ holds.

Definition 1..2   The generalized word problem for $({\cal E},\longrightarrow)$ and ${\cal E}_1 \subseteq {\cal E}$ is to decide for $a\in{\cal E}$, whether there exists $b\in{\cal E}_1$ such that $a \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ holds..

Instances of these problems are well-known in the literature and undecidable in general, but we will outline sufficient conditions such that $({\cal E},\longrightarrow)$ has solvable word problem.

An element $a\in{\cal E}$ is said to be reducible (with respect to $\longrightarrow$) if there exists an element $b \in {\cal E}$ such that $a \longrightarrow b$. All elements $b \in {\cal E}$ such that $a \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ are called successors of a and in case $a \mbox{$\,\stackrel{+}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ they are called proper successors. An element which has no proper successor is called irreducible. In case $a \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } b$ and b is irreducible, b is called a normal form of a. Notice that for an element a in ${\cal E}$ there can be no, one or many normal forms.

Definition 1..3   A reduction system $({\cal E},\longrightarrow)$ is said to be Noetherian (or terminating) in case there are no infinitely descending reduction chains $a_0 \longrightarrow a_1 \longrightarrow\ldots\;$ with $a_i \in {\cal E}$, $i \in {\bf N}$.

In case $({\cal E},\longrightarrow)$ is Noetherian every element in ${\cal E}$ has at least one normal form.

Definition 1..4   A reduction system $({\cal E},\longrightarrow)$ is called confluent, if for all $a, a_1, a_2 \in {\cal E}$, $a \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_1$ and $a \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_2$ implies the existence of $a_3 \in {\cal E}$ such that $a_1 \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_3$ and $a_2 \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_3$.

In case $({\cal E},\longrightarrow)$ is confluent every element has at most one normal form. We can combine these two properties to give sufficient conditions for the solvability of the word problem.

Definition 1..5   A reduction system $({\cal E},\longrightarrow)$ is said to be complete or convergent in case it is both, Noetherian and confluent.

Convergent reduction systems with effective⁶ reduction relations have solvable word problem, as every element has a unique normal form and two elements are equal if and only if their normal forms are equal. Of course we cannot always expect $({\cal E},\longrightarrow)$ to be convergent. Even worse, both properties are undecidable in general. Nevertheless, there are weaker conditions which guarantee convergence.

Definition 1..6   A reduction system $({\cal E},\longrightarrow)$ is said to be locally confluent, if for all $a, a_1, a_2 \in {\cal E}$, $a \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_1$ and $a \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_2$ implies the existence of an element $a_3 \in {\cal E}$ such that $a_1 \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_3$ and $a_2 \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{}\,$ } a_3$.

Now Newman's lemma gives an important connection between confluence and local confluence.

Lemma 1..7 (Newman)   Let $({\cal E},\longrightarrow)$ be a Noetherian reduction system.
Then $({\cal E},\longrightarrow)$ is confluent if and only if $({\cal E},\longrightarrow)$ is locally confluent.

Therefore, if the reduction system is terminating, a check for confluence can be reduced to a check for local confluence. It is often the case that the test for local confluence is a finitary one, hence leading to "critical-pair" based completion procedures. In case the test for local confluence fails for a pair, the reduction relation is refined without changing the generated equivalence relation but preserving termination. This is e.g. done for the critical pairs in the Knuth-Bendix completion procedure and for the s-polynomials in Buchberger's algorithm.

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 ${\bf R}$ be a ring with a reduction $\Longrightarrow_B$ associated with subsets $B \subseteq{\bf R}$ satisfying the following axioms

(A1)

$\Longrightarrow_B\; = \bigcup_{b \in B} \Longrightarrow_{b}$, $\Longrightarrow_B$ is terminating for all subsets $B \subseteq{\bf R}$.

(A2)

$a \Longrightarrow_{b} c$ implies $a - c \in {\sf ideal}_{}^{}(b)$.

(A3)

$a \Longrightarrow_{a} 0$ for all $a \in {\bf R} \backslash \{ 0 \}$.

Notice that in case R is commutative (A2) implies $c = a - b \cdot r$ for some $r \in {\bf R}$. In the non-commutative case in general we get $c = a - \sum_{i=1}^k r_{i1} \cdot b \cdot r_{i2}$ for some $r_{i1}, r_{i2} \in {\bf R}$, $1 \leq i \leq k$ or we can define a more restricted form of reduction by demanding $c = a - r_1 \cdot b \cdot r_2$ for some $r_1, r_2 \in {\bf R}$.

Further let ${\imath}={\sf ideal}_{}^{}(B)$ be the ideal generated by the set B in ${\bf R}$. If $\equiv_{\imath}$ denotes the congruence generated by $\imath$, from (A1) and (A2) $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{B}\,$ } \subseteq \;\;\equiv_{\imath}$ follows. One method for solving the membership problem for $\imath$ by reduction methods is to transform B into a finite set B' such that $\Longrightarrow_{B'}$ is confluent on $\imath$. Notice that 0 has to be irreducible for all $\Longrightarrow_{a}$, $a \in {\bf R}$. Therefore, 0 will be chosen as the normal form of the ideal elements. Hence the goal is to achieve $a \in {\imath}$ if and only if $a \mbox{$\,\stackrel{*}{\Longrightarrow}\!\!\mbox{}^{{\rm }}_{B'}\,$ } 0$. In particular B' also generates $\imath$ and $\imath$ is one equivalence class of $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{B'}\,$ }$. The different definitions of reductions in rings existing in literature show that for solving the membership problem it is not necessary to enforce $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{B'}\,$ } = \;\;\equiv_{\imath}$. E.g. the D-reduction notion given by Pan in [Pa85] does not have this property but it suffices to decide $\equiv_{\imath}$-equivalence of two elements because $a \equiv_{\imath} b$ if and only if $a-b \in {\imath}$. It may happen that D-reduction is not only confluent on $\imath$ but confluent everywhere and still $a \equiv_{\imath} b$ 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 $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{B}\,$ } = \;\;\equiv_{{\sf ideal}_{}^{}(B)}$ holds.

Definition 1..8   A subset B of ${\bf R}$ is called a G-basis of an ideal $\imath$, if $\mbox{$\,\stackrel{*}{\Longleftrightarrow}\!\!\mbox{}^{{\rm }}_{B}\,$ } = \;\;\equiv_{\imath}$ and $\mbox{$\,\stackrel{}{\Longrightarrow}\!\!\mbox{}^{{\rm }}_{B}\,$ }$ is confluent.

${\bf R}$ is called a  reduction ring if every finitely generated ideal has a finite G-basis.
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 ${\bf R}$ satisfies an additional axiom strongly related to interreduction.

(A4)

$a \Longrightarrow_{b}$ and $b\Longrightarrow_{c} d$ imply $a \Longrightarrow_{c}$ or $a \Longrightarrow_{d}$.

Now the question arises which ring constructions, as e.g. extensions, products or quotients, preserve the property of being a reduction ring.

Theorem 1..9   Let ${\bf R}$ be a Noetherian reduction ring. Then ${\bf R}[X_1, \ldots, X_n]$ is a Noetherian reduction ring.

Theorem 1..10   Let ${\bf R}$ be a reduction ring satisfying (A4) and $\imath$ a finitely generated ideal in ${\bf R}$. Then ${\bf R}/{\imath}$ is a reduction ring satisfying (A4).

Theorem 1..11   Let ${\bf R}_1,{\bf R}_2$ be reduction rings. Then the sum ${\bf R}_1 \times {\bf R}_2 = \{(r_1,r_2) \mid r_1 \in {\bf R}_1, r_2 \in {\bf R}_2 \}$ is a reduction ring.

Of course for every such construction an appropriate notion of reduction has to be found which arises naturally in these cases. Another interesting question is, when and how a given algorithm for computing G-bases for a reduction ring can be lifted when constructing new reduction rings. This is possible in all three cases given above and was also studied by Buchberger and Stifter who gave an axiomatic description of the properties necessary to enable such a lifting.
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 ${\bf Z}_m$ for some $m \in {\bf N}^+$. Then the polynomial ring ${\bf Z}_m[X_1, \ldots, X_n]$ again is a reduction ring. Reduction in ${\bf Z}_m[X_1, \ldots, X_n]$ on one hand can be defined by lifting the reduction given in ${\bf Z}_m$ (compare theorem 1.9). But we can also view ${\bf Z}_m[X_1, \ldots, X_n]$ as a quotient, namely ${\bf Z}[X_1, \ldots, X_n]/(m)$, and lift a reduction defined for the polynomial ring ${\bf Z}[X_1, \ldots, X_n]$ 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 $\Sigma$ and a set of rules $T \subseteq \Sigma^* \times \Sigma^*$⁷. We write $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$ if and only if $u \equiv xly$ and $v \equiv xry$ for some $(l,r) \in T$, $x,y \in \Sigma^*$. $\mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$ is the reflexive and transitive closure of $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$. Every monoid ${\cal M}$ can be presented by a semi-Thue system $(\Sigma, T)$, where $\Sigma$ is an alphabet and T a set of rules. One only has to choose $\Sigma = {\cal M}$ 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 $\lambda$ 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 $\Sigma$ is finite and T is finite, confluent and Noetherian, i.e., each word in $\Sigma^*$ has a unique normal form with respect to T. Furthermore, we require the existence of a total, well-founded ordering $\succeq$ which is admissible⁸ on $\Sigma^*$ such that for all $(l,r) \in T$, $l \succ r$ holds. This ordering is called a completion ordering of $(\Sigma, T)$. The monoid ${\cal M}$ is isomorphic to the set ${\rm IRR}\/(T)$ of words irreducible with respect to T. The empty word $\lambda \in\Sigma^*$ presents the identity of ${\cal M}$. The word problem is solvable, which is essential for computation in ${\bf K}[{\cal M}]$. Multiplication of two terms $u,v \in {\cal M}$ is defined by $u \circ v = (uv)\!\!\downarrow_{T}$. The completion ordering of the presentation induces an ordering $\succeq$ on ${\cal M}$ such that for $u,v \in {\cal M}$ we get $u \succeq \lambda$ and $uv \succeq u \circ v$.

The elements of a monoid ring ${\bf K}[{\cal M}]$ over a field ${\bf K}$ can be presented as ``polynomials'' $f = \sum_{m \in {\cal M}} \alpha_{m} \cdot m$ where only finitely many coefficients are non-zero. Addition and multiplication for two polynomials $f = \sum_{m \in {\cal M}} \alpha_{m} \cdot m$ and $h = \sum_{m \in {\cal M}} \beta_{m} \cdot m$ is defined as $f + h = \sum_{m \in {\cal M}} (\alpha_{m} + \beta_{m}) \cdot m$ and $f \ast h = \sum_{m \in {\cal M}} \gamma_{m} \cdot m$ with $\gamma_{m} = \sum_{x \circ y = m \in {\cal M}} \alpha_{x} \cdot\beta_{y}$. For a subset F of ${\bf K}[{\cal M}]$ we call the set ${\sf ideal}_{r}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, w_i \in {\cal M}\}$ the right ideal and ${\sf ideal}_{}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot u_i \ast f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, u_i, w_i \in {\cal M}\}$ the two-sided ideal generated by F. We will henceforth always assume that the field ${\bf K}$ 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 ${\bf K}[{\cal M}]$. 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].