| Algebraic Simplification |
Algebraic simplification aims to rewrite elements of some algebraic structure into equivalent but simpler elements and to distinguish certain elements as representatives. An important goal is the effective (i.e. algorithmic) determination of canonical representatives for an equivalence class of elements. This process is known as Canonical Simplification. It plays an important role in Computer Algebra as it is an essential part of effective calculation in algebraic structures and of decidability issues like the word problem.
Techniques of algebraic simplification have been successfully employed for presenting monoids and groups by String Rewriting Systems or Semi-Thue Systems. String rewriting systems may be 'completed' by the Knuth-Bendix Algorithm. Finite complete presentations always allow canonical simplification and unique representatives for the associated monoid or group. But not all presentations can be completed. This is e.g. the case for presentations of monoids or groups with an undecidable word problem. Depending on the structure of a string rewriting system or on the knowledge about the presented monoid or group specialized variants of the Knuth-Bendix algorithm can be applied. This often leads to considerably more efficient (in terms of memory consumption and run time) completion computations.
Complete string rewriting systems are also a prerequisite for a host of algorithms for the solution of other problems in monoids and groups besides the word problem, e.g. "Is the monoid or the group commutative?," "Is the monoid or group finite?," "Is the group a free group? If so, what are its free generators?," "Does the monoid have nontrivial regular elements?," or the validity problem for linear sentences. Many of these algorithms are based on algorithms dealing with regular languages, finite automata, and push-down automata.
After a multitide of theoretical results have been obtained in the past the demand arose for software systems that provide implementations of all known algorithms and an environment for working with monoids and groups. With additional funding by the Deutsche Forschungsgemeinschaft we now construct the system XSSRin collaboration with with Prof. Otto's research group at the University of Kassel.
Ein weiteres Feld, in dem die Idee algebraischer Simplifikationsmethoden Anwendung gefunden hat, sind Polynomringe über Körpern: 1965 wurde von Buchberger im Rahmen seiner Dissertation das Konzept der Gröbnerbasen für Ideale in Polynomringen über Körpern entwickelt. Gröbnerbasen sind endliche Idealbasen bezüglich derer ein kanonischer Simplifikationsprozeß möglich ist. Dabei wird ein Polynom p mit einem anderen Polynom f simplifiziert (beziehungsweise reduziert genannt), falls ein geeignetes Monomvielfaches von f benutzt werden kann, um p durch Subtraktion zu verkleinern (bezüglich einer sogenannten zulässigen Ordnung). Benutzt man in diesem Simplifikationsprozeß nur Elemente einer Gröbnerbasis eines Ideals, so erhält man eindeutige Repräsentanten bezüglich der Idealkongruenz und der Repräsentant der Idealelemente ist die Null. Buchberger gab in seiner Arbeit ein effektives Verfahren, den sogenannten Buchberger-Algorithmus, an, um eine Idealbasis in eine endliche Gröbnerbasis zu transformieren. Implementierungen dieses Algorithmus sind in vielen Computer-Algebra-Systemen vorhanden (z.B. in Maple, Mathematica und REDUCE). Kanonische Simplifikation mit Gröbnerbasen wird in der Praxis benutzt, um idealtheoretische Probleme in Polynomringen zu lösen. Die Anwendungen reichen vom effektiven Rechnen in Quotientenringen, über das Lösen von Polynomgleichungen, das Untersuchen von Nullstellengebilden bis hin zur Eliminationstheorie, dem geometrischen Beweisen, dem ganzzahligen Optimieren und der Codierungstheorie.
Auch in anderen algebraischen Strukturen interessiert man sich für sogenannte Moduln oder Ideale und sucht nach Wegen, algebraische Simplifikationsmethoden zur effektiven Lösung von Problemen einzusetzen. Von besonderem Interesse sind dabei die Monoid- und Gruppenringe. Hier werden algebraische Simplifikationsmethoden eingesetzt, um zum einen das effektive Rechnen im Monoid oder der Gruppe zu realisieren und zum anderen durch den Einsatz von Gröbnerbasen Ideale oder Moduln zu behandeln. Moduln über Gruppenringen spielen eine wichtige Rolle bei der Berechnung von Quotienten von endlich dargestellten Gruppen. Ein Überblick über die hierbei benutzten Methoden findet sich in der Arbeit von Sims. Für den sogenannten meta-abelschen Fall werden Gröbnerbasen in kommutativen Gruppenringen benötigt; Sims benutzt hierfür Quotienten der Laurent-Polynomringe, die mit herkömmlichen Implementierungen des Buchberger-Algorithmus für kommutative Polynomringe behandelt werden können. Um diese Methode auch für andere Fälle einsetzen zu können, benötigt man eine erfolgreiche Verallgemeinerung der Gröbnerbasenmethoden für nicht-kommutative Gruppenringe und eine Implementierung der dazugehörigen Algorithmen. Die Grundlagen hierfür wurden in unserer Arbeitsgruppe für die Klasse der endlich dargestellten freien Gruppen, die Klasse der endlich dargestellten plain Gruppen, die Klasse der endlich dargestellten kontext-freien Gruppen, die Klasse der endlich dargestellten nilpotenten Gruppen und die Klasse der endlich dargestellten polyzyklischen Gruppen erweitert.
| Research | AG Grundlagen der Informatik | FB Informatik | TU Kaiserslautern |