Computation with finitely L-presented groups
Algorithmen für endlich L-präsentierte Gruppen
von René Hartung
Datum der mündl. Prüfung:2012-06-01
Erschienen:2012-06-20
Betreuer:Prof. Dr. Laurent Bartholdi
Gutachter:Prof. Dr. Laurent Bartholdi
Gutachter:Prof. Dr. Thomas Schick
Dateien
Name:hartung.pdf
Size:1.23Mb
Format:PDF
Zusammenfassung
Englisch
We develop algorithms for certain infinitely presented groups, the so-called finitely L-presented groups. For this purpose, we generalize the well-known algorithms for finitely presented groups to finite L-presentations. For instance, we describe an algorithm for computing the index of a finitely generated subgroup in a finitely L-presented group - provided that this index is finite. Our algorithm generalizes the well-known Todd-Coxeter algorithm for finite presentations. This algorithm has various interesting applications. For instance, it solves the generalized word problem for finite index subgroups of finitely L-presented groups, it allows one to describe a low-index subgroup algorithm, and it yields a method to compute a finite L-presentation for a finite index subgroup of a finitely L-presented group. Furthermore, we prove a generalization of the Reidemeister-Schreier theorem and we generalize the Knuth-Bendix procedure to finite L-presentations.
Keywords: Infinite presentations; recursive presentations; L-presentations; finite index subgroups; algorithms; self-similar groups; Grigorchuk group
Weitere Sprachen
Wir entwickeln Algorithmen für gewisse
unendlich präsentierte Gruppen, die sogenannten endlich
L-präsentierten Gruppen. Hierfür verallgemeinern wir die bekannten
Algorithmen für endlich präsentierte Gruppen. Beispielsweise
beschreiben wir einen Algorithmus zur Berechnung des Index einer
endlich erzeugten Untergruppe in einer endlich L-präsentierten
Gruppe - unter der Voraussetzung, dass dieser Index endlich ist.
Unser Algorithmus verallgemeinert den Todd-Coxeter Algorithmus für
endlich präsentierte Gruppen. Dieser Algorithmus hat viele
interessante Anwendungen: Er liefert eine Lösung des allgemeinen
Wort-Problems für Untergruppen endlichen Index in einer endlich
L-präsentierten Gruppe, er erlaubt die Entwicklung eines
Algorithmus zur Berechnung aller Untergruppen bis zu einem
vorgegebenen endlichen Index in einer endlich L-präsentierten
Gruppe, sowie die Entwicklung einer Methode für die Berechnung
einer endlichen L-Präsentation für eine Untergruppe endlichen Index
in einer endlich L-präsentierten Gruppe. Darüber hinaus beweisen
wir eine Verallgemeinerung des Reidemeister-Schreier Theorems und
verallgemeinern die Knuth-Bendix Prozedur auf endliche
L-Präsentationen.
Schlagwörter: Unendliche Präsentationen; rekursive Präsentationen; L-Präsentationen; Untergruppen endlichen Index; Algorithmen; selbstähnliche Gruppen; Grigorchuk Gruppe.