Abstract:
Following Buchberger's approach to computing a Gröbner 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 Gröbner bases. The connection to the subgroup problem is discussed.

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