Authors
Birgit Reinert
Title
On Gröbner Bases in Monoid and Group Rings
In
PhD Thesis, Fachbereich Informatik, Univ. Kaiserslautern, 1996.
Bibtex Entry
Copyright Owner
None
Abstract
Developed by Bruno Buchberger for commutative polynomial rings, Gröbner Bases are frequently applied to solve algorithmic problems. For instance, the congruence problem for ideals can be solved with the help of Gröbner bases. Until now, these ideas have been transmitted to different in part non-commutative and non-Noetherian algebras. Most of these approaches require an admissible ordering on terms. In this Ph.D. thesis, the concept of Gröbner bases is generalized to finitely generated monoid and group rings. Reduction methods are applied to represent monoid and group elements and to describe the right-ideal congruence in the corresponding monoid and group rings, respectively. In general, monoids and especially groups do not offer admissible orderings anymore. Thus, the definition of an appropriate reduction relation is confronted with the following problems: On the one hand, it is difficult to guarantee termination. On the other hand, reduction steps are not compatible with multiplication anymore, so that the reduction relation does not necessarily generate a right-ideal congruence. In this thesis, several possibilities of defining reduction relations are presented and evaluated w.r.t. the described problems. The concept of saturation (i.e. the extension of a set of polynomials in such a way that the right-ideal congruence it generates can be captured by reduction) is applied to characterize Gröbner bases relatively to the different reductions by s-polynomials. Using these concepts and special structural properties, it was possible to define special reduction relations for special classes of monoids (e.g., finite, commutative, or free) and for different classes of groups (e.g., finite, free, plain, context-free, or nilpotent) and to develop terminating algorithms for computing Gröbner bases w.r.t. these reduction relations. (English translation by Claus-Peter Wirth)

Gröbnerbasen, entwickelt von Bruno Buchberger für kommutative Polynomringe, finden häufig Anwendung bei der Lösung algorithmischer Probleme. Beispielsweise lässt sich das Kongruenzproblem für Ideale mit Hilfe der Gröbnerbasen lösen. Bis heute wurden diese Ideen auf verschiedene zum Teil nichtkommutative und nichtnoethersche Algebren übertragen. Die meisten dieser Ansätze setzen eine zulässige Ordnung auf den Termen voraus. In dieser Dissertation wird das Konzept der Gröbnerbasen für endlich erzeugte Monoid- und Gruppenringe verallgemeinert. Dabei werden Reduktionsmethoden sowohl zur Darstellung der Monoid- beziehungsweise Gruppenelemente, als auch zur Beschreibung der Rechtsidealkongruenz in den entsprechenden Monoid- beziehungsweise Gruppenringen benutzt. Da im allgemeinen Monoide und insbesondere Gruppen 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. Dabei wird das Konzept der Saturierung, d.h. eine Polynommenge so zu erweitern, dass man die von ihr erzeugte Rechtsidealkongruenz durch Reduktion erfassen kann, benutzt, um Charakterisierungen von Gröbnerbasen bezüglich der verschiedenen Reduktionen durch s-Polynome zu geben. Mithilfe dieser Konzepte ist es gelungen 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, unter Ausnutzung struktureller Eigenschaften spezielle Reduktionsrelationen zu definieren und terminierende Algorithmen zur Berechnung von Gröbnerbasen bezüglich dieser Reduktionsrelationen zu entwickeln.

Full paper