| Algebraische Simplifikation |
Ziel algebraischer Simplifikation ist es, Elemente einer algebraischen Struktur in äquivalente, `einfachere' Elemente umzuformen und darüberhinaus gewisse Elemente als Repräsentanten auszuzeichnen. Angestrebt wird dabei die effektive Berechnung eindeutiger Repräsentanten äquivalenter Objekte. Dieser Prozeß wird in der Literatur häufig mit kanonischer Simplifikation bezeichnet. Er spielt eine wichtige Rolle in der Computer-Algebra, da er eng verknüpft ist mit dem effektiven Rechnen in algebraischen Strukturen und der Entscheidung des Wortproblems.
Erfolgreich eingesetzt wird die Technik der algebraischen Simplifikation z.B. bei der Darstellung von Monoiden und Gruppen durch sogenannte Wortersetzungssysteme oder Semi-Thue-Systeme. Solche Wortersetzungssyteme können durch den sogenannten Knuth-Bendix-Algorithmus `vervollständigt' werden. Endliche vollständige Darstellungen erlauben immer kanonische Simplifikation und eindeutige Repräsentanten der zugehörigen Monoide. Jedoch lässt nicht jede Darstellung kanonische Simplifikation zu; dies gilt beispielsweise für Darstellungen von Monoiden und Gruppen mit einem unentscheidbarem Wortproblem. Je nach Struktur eines Wortersetzungssystems oder auch durch Wissen über das dargestellte Monoid oder die dargestellte Gruppe kann man spezialisierte Varianten des Knuth-Bendix-Algorithmus einsetzen, um so eine wesentlich (zeit-/platz-)effizientere Vervollständigung zu erreichen.
Vervollständigte Wortersetzungssysteme sind auch Voraussetzung für eine ganze Reihe von Algorithmen, die neben dem Wortproblem noch weitere Entscheidungsprobleme über die dargestellten Monoide und Gruppen lösen, z.B. "Ist das Monoid bzw. die Gruppe kommutativ?", "Ist das Monoid bzw. die Gruppe endlich?", "Ist die Gruppe eine freie Gruppe? Welches sind freie Erzeugende?", "Gibt es im Monoid nichttriviale reguläre Elemente?" bis hin zum Gültigkeitsproblem für lineare Sätze. Viele dieser Algorithmen basieren auf Algorithmen zur Behandlung von regulären Sprachen, endlichen Automaten und Kellerautomaten.
Nachdem in den vergangenen Jahren eine Vielzahl theoretischer Ergebnisse erzielt werden konnten, kam der Wunsch nach einem Software-System auf, das alle bekannten Algorithmen implementiert und eine Umgebung für das Arbeiten mit Monoiden und Gruppen zur Verfügung stellt. Im Rahmen eines von der DFG geförderten Projektes entsteht zur Zeit das Software-System XSSR in Zusammenarbeit mit der Arbeitsgruppe von Prof. Otto an der Universität 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.
| Forschung | AG Grundlagen der Informatik | FB Informatik | TU Kaiserslautern |