Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-2820
Authors: Kausch, Jonathan
Title: Normalformenberechnung in Graph-Gruppen und Coxeter-Gruppen
Other Titles: Normal form calculations in graph groups and coxeter groups
Issue Date: 2011
metadata.ubs.publikation.typ: Abschlussarbeit (Diplom)
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-73789
http://elib.uni-stuttgart.de/handle/11682/2837
http://dx.doi.org/10.18419/opus-2820
Abstract: Im Rahmen der Diplomarbeit wurde das Normalformenproblem für partiell kommutative Gruppen in logarithmischem Platz untersucht. Diese Gruppen sind in der Mathematik als Graph-Gruppen oder "rechtwinklige Artingruppen" bekannt und werden u.a. in der kombinatorischen Gruppentheorie untersucht. In der Informatik erscheinen sie als natürliche Erweiterung der Spurmonoide, die von Keller und Mazurkiewicz eingeführt wurden und insbesondere für die Untersuchung von Nebenläufigkeit in der Informatik von Bedeutung sind. Zur Analyse der Normalformenproblemberechnung werden die Graph-Gruppen zunächst in rechtwinklige Coxeter-Gruppen eingebettet. Für beliebige Coxeter-Gruppen kann das Alphabet der längenlexikographischen Normalform in logarithmischem Platz bestimmt werden. Darauf aufbauend kann die längenlexikographische Normalform in rechtwinkligen Coxeter-Gruppen berechnet werden. Für allgemeine Coxeter Gruppen wird in "Combinatorics of Coxeter Groups" (Björner, Brenti) ein Algorithmus vorgestellt, der die Normalform mit linear vielen reellen arithmetischen Operationen und Vergleichen bestimmt. Die Berechnung lässt sich allerdings nicht ausschließlich mit ganzen Zahlen durchführen, sondern es werden komplexe Einheitswurzeln benötigt. In dieser Arbeit wird geklärt, wie viele Bits zur Repräsentation notwendig sind. Außerdem wird ein elementarer Beweis angegeben, der zeigt, dass für Coxeter-Gruppen ein präperfektes Ersetzungssystem existiert. Ein präperfektes Ersetzungssystem ist ein Ersetzungssystem, welches nur längenerhaltende und längenreduzierende Regeln besitzt. Coxeter-Gruppen gehören unter anderem zur Klasse der automatischen Gruppen. Für rechtwinklige Coxeter-Gruppen wird in dieser Arbeit ein Beweis angegeben, der zeigt, dass diese automatisch sind.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
DIP_3238.pdf355,14 kBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.