Automatic presentations of infinite structures

• Automatische Darstellungen von unendlichen Strukturen

Bárány, Vince; Grädel, Erich (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2007)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2007

Kurzfassung

In dieser Arbeit werden die Möglichkeiten zur Darstellung unendlicher Strukturen mithilfe von endlichen Automaten sowie die Grenzen dieser Methode untersucht. Eine automatische Darstellung einer abzählbaren Struktur besteht aus einer Beschriftung der Elemente der Struktur mit endlichen Wörtern über einem endlichen Alphabet in einer konsistenten Art und Weise, so dass jede Relation der Struktur, in der gewählten Beschriftung, sich durch einen synchronen vielbändigen Automaten erkennen lässt. Ein Tupel geeigneter Automaten, einer für jede Relation, liefert eine endliche, bis auf Isomorphie eindeutige Beschreibung der Struktur. Allgemeiner kann man Darstellungen über endlichen Bäumen oder über unendlichen Wörtern oder Bäumen betrachten. Letztere sind auch geeignet überabzählbare Strukture zu beschreiben. Infolge klassischer Korrespondenzen zwischen Logiken und Automaten wird eine algorithmische Auswertung logischer Formeln erster Stufe über jeder einzelnen durch Automaten dargestellten Struktur möglich. Ferner kann man automatische Präsentationen in logische Interpretationen übersezten bzw. als solche wahrnehmen. Die Einfachheit und Robustheit dieses Modells und die Vielfalt automatischer Strukturen motivieren eine ausführlichere Untersuchung automatischer Präsentationen in Rahmen der algorithmischen Modelltheorie. Obwohl Automaten längst zur Darstellung unendlicher Strukturen in diversen Bereichen, u.a. in der algorithmischen Gruppentheorie, Zahlensysteme, endlich generierten undendlichen Folgen und Termersetzungssysteme in Gebrauch gewesen sind, wurde erst vor etwa zwölf Jahren eine systematische Untersuchung automatischer Strukturen mithilfe modelltheoretischer Methoden veranlasst. Zwei wichtige Forschungsrichtungen werden in diesem Bereich sichtbar. Einerseits wird eine Klassifizierung automatischer Modelle bestimmter Theorien erster Stufe von allgemeinerer Bedeutung, wie z.B. lineare Ordnungen, Bäume, Boolsche Algebren, Gruppen usw. angestrebt. Trotz anhaltender Bemühungen struktursche Sätze zu finden und früher Erfolge befindet sich dieses Programm noch in der Anfangsphase. Noch mangelhafter ist unser Verständnis der reichen Möglichkeiten verschiedener automatischer Darstellungen einzelner Strukturen von zentraler Bedeutung. Ein prominentes Ergebnis in diesem zweiten Bereich ist der tiefgehende Satz von Cobham und Semenov über wohl bekannte Zahlensysteme. In dieser Tradition wollen wir den Freiheitsgrad der Wahl einer automatischen Pr¨asentation gewisser Strukturen genauer verstehen. In dieser Dissertation werden Beiträge zu den beiden erwähnten Problembereichen vorgelegt, mit Schwerpunkt auf dem letzteren. Ferner werden eingeschränkte Präsentationen untersucht und das Verhältnis automatischer Darstellungen über endlichen Wörtern im Vergleich zur Präsentationen mit unendlichen Wörtern geklärt. Die Eigentümlichkeiten des Gebrauchs von Automaten zur Darstellung von Strukturen bis auf Isomorphie erzeugen Probleme ausserhalb der Reichweite klassischer Automatentheorie. Es werden einige neue Techniken zur Bewältigung dieser Schwerigkeiten präsentiert.