On Groebner Bases in Monoid and Group Rings

K. Madlener, B. Reinert
Fachbereich Informatik, Universitaet Kaiserslautern
D-67653 Kaiserslautern, Germany
E-mail: madlener@informatik.uni-kl.de, reinert@informatik.uni-kl.de

Abstract
Following Buchberger's approach to computing a Groebner basis of a polyn
omial ideal in polynomial rings,
a completion procedure for finitely generated right ideals in Z[H] is given,
where H is an ordered monoid presented by a finite, convergent semi--Thue
System (Sigma,T).
Taking a finite subset F of Z[H] we get a (possibly infinite) basis of the right
ideal generated by F, such that using this basis we have unique normal
forms for all p in  Z[H] (especially  the normal form is 0 in case p
is an element of the right ideal generated by F).
As the ordering and multiplication on H need not be compatible, reductio
n has to be defined carefully in order to make it Noetherian.
Further we no longer have that the product of p and x reduces to 0 for p
in Z[H], x in H.
Similar to Buchberger's s-polynomials, confluence criteria are developed
and a completion procedure is given.
In case T is empty or (Sigma,T) is a convergent, 2-monadic presentation
of a group providing inverses of length 1 for the generators or (Sigma,T)
is a convergent presentation of a commutative monoid, termination can be shown.
So in this cases finitely generated right ideals admit finite Groebner bases.
The connection to the subgroup problem is discussed.


Keywords
Reduction, Groebner bases, monoid and group rings, subgroup problem.

Source
anonymous FTP server ftp.uni-kl.de [131.246.94.94]
path: /reports_uni-kl/computer_science/SEKI/1993/papers/
file: Reinert.SR-93-08.ps.Z