Relating Rewriting Techniques on Monoids and Rings:
Congruences on Monoids and Ideals in Monoid Rings

Klaus Madlener and Birgit Reinert¹
Fachbereich Informatik
Universität Kaiserslautern
67663 Kaiserslautern
Germany
{madlener,reinert}@informatik.uni-kl.de

September, 1997

Abstract:

A first explicit connection between finitely presented commutative monoids and ideals in polynomial rings was used 1958 by Emelichev yielding a solution to the word problem in commutative monoids by deciding the ideal membership problem. The aim of this paper is to show in a similar fashion how congruences on monoids and groups can be characterized by ideals in respective monoid and group rings. These characterizations enable to transfer well known results from the theory of string rewriting systems for presenting monoids and groups to the algebraic setting of subalgebras and ideals in monoid respectively group rings. Moreover, natural one-sided congruences defined by subgroups of a group are connected to one-sided ideals in the respective group ring and hence the subgroup problem and the ideal membership problem are directly related. For several classes of finitely presented groups we show explicitly how Gröbner basis methods are related to existing solutions of the subgroup problem by rewriting methods. For the case of general monoids and submonoids weaker results are presented. In fact it becomes clear that string rewriting methods for monoids and groups can be lifted in a natural fashion to define reduction relations in monoid and group rings.