Automatic presentations of infinite structures [Elektronische Ressource] / vorgelegt von Vince Bárány

Sujets

• Informatik
• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2007
• Nombre de lectures: 4
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Automatic Presentations of Infinite Structures
Vince B´ar´anyAutomatic Presentations of Infinite Structures
Von der Fakult¨at fu¨r Mathematik, Informatik und Naturwissenschaften der
Rheinisch-Westf¨alischen Technischen Hochschule Aachen zur Erlangung des
akademischen Grades eines Doktors der Naturwissenschaften genehmigte
Dissertation
vorgelegt von
Vince B´ar´any, M.Sc.
aus Budapest, Ungarn
Berichter: Universit¨atsprofessor Dr. Erich Gr¨adel
´Universit¨atsprofessor Dr. Jean-Eric Pin
Tag der mu¨ndlichen Pru¨fung: 5. September 2007
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online
verfu¨gbar.Abstract
The work at hand studies the possibilities and limitations of the use of finite
automata in the description of infinite structures. An automatic presentation of a
countable structure consists of a labelling of the elements of the structure by finite
words over a finite alphabet in a consistent way so as to allow each of the relations
of the structure to be recognised, given the labelling, by a synchronous multi-tape
automaton. The collection of automata involved constitutes a finite presentation of
the structure up to isomorphism. More generally, one can consider presentations
over finite trees or over infinite words or trees, based on the appropriate model of
automata. In the latter models, uncountable structures are also representable.
Automatic presentations allow for effective evaluation of first-order formulas over
the represented structure in line with the strong correspondence between automata
and logics. Accordingly, automatic presentations can be recast in logical terms
using various notions of interpretations. The simplicity and robustness of the model
coupled with the diversity of automatic structures makes automatic presentations
interesting subject of investigation within the scope of algorithmic model theory.
Although automata have been in use in representations of infinite structures in
computational group theory, in the analysis of numeration systems and finitely gen-
erated infinite sequences as well as in the theory of term rewriting systems, a sys-
tematic investigation of automatic structures using model theoretic methods has
only just begun in the last twelve years.
There are two main lines of research in this field. One would like to have a classi-
fication of automatic models of certain first-order theories of common interest, such
as linear orderings, trees, boolean algebras, groups, etc. Though efforts aimed at ob-
taining structure theorems have produced considerable advancement in recent years,
this programme is still in an early stage. Even further lacking is our understanding
of the richness of automatic presentations of key individual structures. A prominent
result in this area is the deep theorem of Cobham and Semenov concerning numera-
tion systems. In this style, one would like to know the degree of freedom in choosing
automatic presentations of a particular structure.
In this thesis we present contributions to both of these problem areas. We also
study restricted notions of presentations and clarify the relationship of automatic
presentations over finite and infinite words. The peculiarities of using automata
to represent structures up to isomorphism introduce problems out of the range of
classical automata theory. We present some new techniques developed to tackle
these difficulties.
iZusammenfassung
In dieser Arbeit werden die M¨oglichkeiten zur Darstellung unendlicher Struk-
turen mithilfe von endlichen Automaten sowie die Grenzen dieser Methode unter-
sucht. Eine automatische Darstellung einer abz¨ahlbaren Struktur besteht aus einer
Beschriftung der Elemente der Struktur mit endlichen W¨ortern u¨ber einem endlichen
Alphabet in einer konsistenten Art und Weise, so dass jede Relation der Struktur, in
der gew¨ahlten Beschriftung, sich durch einen synchronen vielb¨andigen Automaten
erkennen l¨asst. Ein Tupel geeigneter Automaten, einer fu¨r jede Relation, liefert eine
endliche, bis auf Isomorphie eindeutige Beschreibung der Struktur. Allgemeiner
kann man Darstellungen u¨ber endlichen B¨aumen oder u¨ber unendlichen W¨ortern
oder B¨aumen betrachten. Letztere sind auch geeignet u¨berabz¨ahlbare Strukture zu
beschreiben.
Infolge klassischer Korrespondenzen zwischen Logiken und Automaten wird eine
algorithmische Auswertung logischer Formeln erster Stufe u¨ber jeder einzelnen durch
Automaten dargestellten Struktur m¨oglich. Ferner kann man automatische Pr¨asen-
tationen in logische Interpretationen u¨bersezten bzw. als solche wahrnehmen. Die
Einfachheit und Robustheit dieses Modells und die Vielfalt automatischer Struk-
turen motivieren eine ausfu¨hrlichere Untersuchung automatischer Pr¨asentationen in
Rahmen der algorithmischen Modelltheorie.
Obwohl Automaten l¨angst zur Darstellung unendlicher Strukturen in diversen
Bereichen, u.a. in der algorithmischen Gruppentheorie, Zahlensysteme, endlich gener-
ierten undendlichen Folgen und Termersetzungssysteme in Gebrauch gewesen sind,
wurde erst vor etwa zw¨olf Jahren eine systematische Untersuchung automatischer
Strukturen mithilfe modelltheoretischer Methoden veranlasst.
Zwei wichtige Forschungsrichtungen werden in diesem Bereich sichtbar. Einer-
seits wird eine Klassifizierung automatischer Modelle bestimmter Theorien erster
Stufe von allgemeinerer Bedeutung, wie z.B. lineare Ordnungen, B¨aume, Boolsche
Algebren, Gruppen usw. angestrebt. Trotz anhaltender Bemu¨hungen struktursche
S¨atze zu finden und fru¨her Erfolge befindet sich dieses Programm noch in der An-
fangsphase. Noch mangelhafter ist unser Verst¨andnis der reichen M¨oglichkeiten ver-
schiedener automatischer Darstellungen einzelner Strukturen von zentraler Bedeu-
tung. Ein prominentes Ergebnis in diesem zweiten Bereich ist der tiefgehende Satz
von Cobham und Semenov u¨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¨age zu den beiden erw¨ahnten Problembere-
ichen vorgelegt, mit Schwerpunkt auf dem letzteren. Ferner werden eingeschr¨ankte
Pr¨asentationen untersucht und das Verh¨altnis automatischer Darstellungen u¨ber
endlichen W¨ortern im Vergleich zur Pr¨asentationen mit unendlichen W¨ortern gekl¨art.
Die Eigentu¨mlichkeiten des Gebrauchs von Automaten zur Darstellung von Struk-
turen bis auf Isomorphie erzeugen Probleme ausserhalb der Reichweite klassischer
Automatentheorie. Es werden einige neue Techniken zur Bew¨altigung dieser Schw-
erigkeiten pr¨asentiert.
iiAcknowledgement I am most grateful to Erich Gr¨adel for giving me the oppor-
tunity to pursue my interests, for introducing me into an inspiring international
community of researchers, and for his continued support throughout my work. For
the excellent working and learning environment I am equally grateful to Wolfgang
Thomas, and also to Renate Eschenbach-Thomas and her team for creating a won-
derful atmosphere at the Informatik Bibliothek and for acquiring even the rarest of
references.
I have gained much from collaboration with L ukasz Kaiser, Christof L¨oding, Sasha
Rubin, and Olivier Serre. In addition I thank Arnaud Carayol, Didier Caucal,
Thomas Colcombet, and Luc Segoufin for their illuminating thoughts which have
contributed to this thesis in many ways.
Very special thanks to my brother-in-arms L ukasz once more for his insightful
remarks at every stage of my work and for his companionship during the last forty
some months. Similarly, to Sasha, for always being ready to discuss whatever i had
on my mind. Additionally, I am particularly grateful to Arnaud Carayol, Tobias
Ganzow, Christof L¨oding and Michael Ummels for careful corrections to this text.
I thank my friends and colleagues Alex, Dietmar, Jan, Kari, Michael, Nico,
Philipp, Stefan, also Bernd, Diana, Fr´ed´eric, Henrik, Roman, Wenyun, the respected
members of the hungarian football team: D´enes, Feri, Gergo˝, Norbert, Roland,
Tam´as, as well as my dear friends Bal´azs, Kata, Mathis, Jutka, Petra, and the
Breuer family heartily for making me feel at home in Aachen. My heart goes to
´those at home or abroad Akos, Andr´as, Misi, Orsi, Tam´as, and to my loved ones for
spoiling me with their love, trust and constant encouragement and to Panni for all
that we share.
iiiivContents
1 Introduction 1
1.1 From finite to algorithmic model theory . . . . . . . . . . . . . . . . . 1
1.1.1 Automatic structures . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Transition graphs of infinite state processes . . . . . . . . . . . 5
1.2 Outline of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Preliminaries 11
2.1 Words and trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Finite automata on finite words . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Multi-tape automata . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Semi-synchronous Rational Relations . . . . . . . . . . . . . . 13
2.2.3 Rational Tra