Abstract:
A first explicit connection between finitely presented commutative monoids and ideals in polynomial rings was used 1958 by Emelichev yielding a solution for the word problem in commutative monoids by deciding the ideal membership problem. The aim of this paper is to show how congruences on monoids and groups can be characterized by ideals in the corresponding monoid and group rings. These characterizations allow 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 and 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 that are based on 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 way to define reduction relations in monoid and group rings.

Klaus Madlener, Birgit Reinert
Fachbereich Informatik
Postfach 3049
67653 Kaiserslautern, Germany