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 f1 = X12 + X2 and f2 = X12 + X3 be two polynomials in the polynomial ring3 . Then is the ideal they generate and it is not hard to see that the polynomial X2 - X3 belongs to since X2 - X3 = f1 - f2. But what can be said about the polynomial f = X33 + X1 + X3? 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 = X33 + X1 + X3 we find that it cannot belong to since neither X12 nor X2 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 Xj is multiplied with a variable Xi with lower index, i.e., i<j. In the latter case multiplication can be defined by equations of the form where and pij is a polynomial ``smaller'' than XiXj with respect to a fixed admissible term ordering on the polynomial ring.
The more special case of twisted semi-group rings, where cij = 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 zero4.
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 multiplication5. 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 cij = 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.
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
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.
It is often useful, if satisfies an additional axiom strongly related to interreduction.
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 admissible8 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.
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.
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].