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)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2007

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 generated infinite sequences as well as in the theory of term rewriting systems, a systematic 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 classification of automatic models of certain first-order theories of common interest, such as linear orderings, trees, boolean algebras, groups, etc. Though efforts aimed at obtaining 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 numeration 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.