Besides the word problem, the subgroup problem or generalized word problem is another classical important well studied 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 the corresponding completion method 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].
The application of reduction techniques in rings for solving membership problems of ideals and subalgebras also has a long tradition and has produced multiple results beginning with Buchberger's fundamental work on Gröbner bases [Bu65].
The main purpose of this paper is to relate the reduction techniques used for monoids, groups and rings by explicitly relating decision problems in appropriate related structures. Using reductions, e.g. from the word problem for finitely presented monoids or groups to the ideal membership problem for corresponding free monoid or free group rings, the apparently different reduction techniques for solving the problems can be compared. We survey some results concerning the above mentioned decision problems. A survey on reduction techniques for rings can be found in [MaRe95]. A first connection between (finitely presented) commutative monoids and polynomial rings can be found in the work of Emelichev 1958 (see e.g. [MaMeSa93]). He gives a solution for the word problem in commutative monoids using algebraic methods. 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 a result of Hermann 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. Polynomials are used as rules by giving an admissible term ordering on the terms and using the largest monomial according to this ordering as a left-hand side of a rule. ``Reduction'' defined in this way can be interpreted as division of one polynomial by a set of finitely many polynomials. A Gröbner basis now can be defined as a set of polynomials G 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 enabling to solve the membership problem for ideals).
In this paper we want to show how congruences on monoids and groups
are connected to ideals in the respective monoid and group rings.
These connections enable to transfer results from the former field
to generalizations of Gröbner basis methods in various structures.
In [Re95] we 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 [Mo85]
of Buchberger's algorithm for free monoid rings.
These results are summarized in section 3
after giving some basic notions in section 2.
Moreover, the subalgebra respectively one-sided ideal
membership problem in monoid respectively group rings are related
to the submonoid respectively subgroup problem in monoids respectively
In section 4 and 5 we show the relations between Gröbner
bases in group rings and rewriting techniques for
the word and subgroup problem in groups.
Section 6 outlines the more general case of subalgebras in
monoid rings, and the connections to the submonoid problem in the
corresponding monoid are studied.
While the results presented in these sections make clear that only
very restricted types of monoids or groups will allow finite Gröbner bases
in the associated monoid or group rings, in the concluding remarks
we collect known positive results on the existence of finite Gröbner bases
in some group rings,
which prove that for the groups known to have subgroup problems solvable
by string rewriting methods, appropriate finite Gröbner bases can be
defined in the respective group ring.
These classes of finitely presented groups include the finite, the free, the
plain, the context-free respectively the polycyclic groups, and the details
can be found in [MaRe95].
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.