1. Introduction

The development of symbolic computation theory - a field related to mathematics as well as to computer science - has resulted in new constructive approaches to computational problems in algebra in particular for rings, monoids and groups. Especially reduction techniques provide concepts for representing congruences by rewriting systems, transform these systems and use them for computations in quotient structures using symbolic methods. For general varieties these techniques have been studied extensively and the general results of term rewriting are widely applied in different areas. Since monoids respectively groups, as examples of varieties, can be presented as quotients of free monoids respectively free groups, general rewriting is one technique to solve computational problems related to the respective structures. Such presentations in terms of generators and defining relations (see e.g. [Gi79,LySch77,MaKaSo76]) are closely related to so called string rewriting systems or semi-Thue systems, which can be seen as special rewriting systems. Hence knowledge and procedures from this field, especially variations of the Knuth-Bendix completion procedure [KnBe70], can be applied to solve monoid and group theoretic problems. The most basic such problem is the word problem, i.e. decide whether two representations of elements in fact describe the same element. This problem can be solved using rewriting techniques in case the Knuth-Bendix completion procedure terminates for a given string rewriting system yielding a finite convergent system. Hence the question which monoids have presentations by finite convergent (i.e. complete) semi-Thue systems and how to compute them is of special interest. Kapur and Narendran in [KaNa85] and Jantzen in [Ja81,Ja85] give examples of monoid presentations which cannot be completed although a finite convergent semi-Thue system over an other alphabet presenting the same monoid exists. Squier proved the existence of finitely presented monoids with decidable word problem which cannot be presented by any finite convergent semi-Thue system [Sq87]. Some characterizations of classes of groups with finite convergent presentations of certain syntactical type can be found in [MaOt89].

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 ${\cal M}$ is presented by a set of generators $x_1, \ldots, x_n$ and a set of defining relations $l_1 = r_1, \ldots, l_m = r_m$ the following is true: A relation u=w holds in ${\cal M}$ if and only if the polynomial u-w lies in the ideal generated by the polynomials $l_1 - r_1, \ldots, l_m - r_m$ in the polynomial ring ${\bf Q}[x_1, \ldots, x_n]$. 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 groups. 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].

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.