Kurzfassung:
In dieser Dissertation wird das Konzept der Gröbnerbasen für endlich erzeugte Monoid- und Gruppenringe verallgemeinert. Dabei werden Reduktionsmethoden sowohl zur Darstellung der Monoidelemente, als auch zur Beschreibung der Rechtsidealkongruenz in den entsprechenden Ringen benutzt. Da im allgemeinen Monoide keine zulässigen Ordnungen mehr erlauben, treten bei der Definition einer geeigneten Reduktionsrelation wesentliche Probleme auf: Zum einen ist es schwierig, die Terminierung einer Reduktionsrelation zu garantieren, zum anderen sind Reduktionsschritte nicht mehr mit Multiplikationen verträglich und daher beschreiben Reduktionen nicht mehr unbedingt eine Rechtsidealkongruenz. In dieser Arbeit werden verschiedene Möglichkeiten Reduktionsrelationen zu definieren aufgezeigt und im Hinblick auf die beschriebenen Probleme untersucht. Für spezielle Klassen von Monoiden, wie z.B. endliche, kommutative oder freie, und verschiedene Klassen von Gruppen, wie z.B. endliche, freie, plain, kontext-freie oder nilpotente, ist es gelungen unter Ausnutzung struktureller Eigenschaften spezielle Reduktionsrelationen zu definieren und terminierende Algorithmen zur Berechnung von Gröbnerbasen bezüglich dieser Reduktionsrelationen zu entwickeln.

Abstract:
In this thesis the concept of Gröbner bases is generalized for finitely generated monoid and group rings. Reduction methods are used to represent the monoid elements as well as to describe the right ideal congruence in the respective rings. Since in general monoids do not allow admissible orderings, in defining suitable reduction relations serious problems arise: on one hand it is difficult to guarantee termination for reduction relations, and on the other hand, reduction does not necessarily capture the right ideal congruence. In this thesis different possible definitions of reduction are given and studied with respect to these problems. For special classes of monoids - e.g. finite, commutative or free - and different classes of groups - e.g. finite, free, plain, context-free or nilpotent - using special structural properties we have succeeded in defining special reduction relations and developing terminating algorithms to compute Gröbner bases with respect to these reduction relations.

Birgit Reinert
Fachbereich Informatik
Postfach 3049
67653 Kaiserslautern, Germany