Pumping for ordinal-automatic structures¹

Article type: Research Article

Authors: Huschenbett, Martin^{a; *} | Kartzow, Alexander^{b; **} | Schlicht, Philipp^c

Affiliations: [a] Institut für Informatik, Ludwig-Maximilians-Universität München, München, Germany. [email protected] | [b] Department für Elektrotechnik und Informatik, Universität Siegen, Siegen, Germany. [email protected] | [c] Institut für Mathematische Logik und Grundlagenforschung, Universität Münster, Münster, Germany. [email protected]

Note: [1] Some of the results have been mentioned in the CiE’13-Paper [In The Nature of Computation. Logic, Algorithms, Applications – 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1–5, 2013. Proceedings, Lecture Notes in Computer Science, Vol. 7921, Springer, 2013, pp. 273–283] by the second and third author.

Note: [*] The results presented here were obtained while the first author was affiliated to Institut für Theoretische Informatik, Technische Universität Ilmenau, Germany.

Note: [**] Supported by the DFG research project GELO.

Abstract: An α-automaton (for α some ordinal) is an automaton similar to a Muller automaton that processes words of length α. A structure is called α-automatic if it can be presented by α-automata (completely analogous to the notion of automatic structures which can be presented by the well-known finite automata). We call a structure ordinal-automatic if it is α-automatic for some ordinal α. We continue the study of ordinal-automatic structures initiated by Schlicht and Stephan as well as by Finkel and Todorčević. We develop a pumping lemma for α-automata (processing finite α-words, i.e., words of length α that have one fixed letter at all but finitely many positions). Using this pumping, we provide counterparts for the class of ordinal-automatic structures to several results on automatic structures: ∙ Every finite word α-automatic structure has an injective finite word α-automatic presentation for all α<ω1+ωω. This bound is sharp. ∙ We classify completely the finite word ωn-automatic Boolean algebras. Moreover, we show that the countable atomless Boolean algebra does not have an injective finite-word ordinal-automatic presentation. ∙ We separate the class of finite-word ordinal-automatic structures from that of tree-automatic structures by showing that free term algebras with at least 2 generators (and one binary function) are not ordinal-automatic while the free term algebra with countable infinitely many generators is known to be tree-automatic. ∙ For every ordinal α<ω1+ωω, we provide a sharp bound on the height of the finite word α-automatic well-founded order forests. ∙ For every ordinal α<ω1+ωω, we provide a structure Fα that is complete for the class of finite-word α-automatic structures with respect to first-order interpretations. ∙ As a byproduct, we also lift Schlicht and Stephans’s characterisation of the injectively finite-word α-automatic ordinals to the noninjective setting.

Keywords: Ordinal-automatic structures, pumping lemma, classification of Boolean algebras, order forests

DOI: 10.3233/COM-160057

Journal: Computability, vol. 6, no. 2, pp. 125-164, 2017