Pumping for ordinal-automatic structures 1

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 $\mathit{\alpha }\mathrm{<}{\mathit{\omega }}_1+{\mathit{\omega }}^{\mathit{\omega }}$ . This bound is sharp.

∙ We classify completely the finite word ${\mathit{\omega }}^{\mathit{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 $\mathit{\alpha }\mathrm{<}{\mathit{\omega }}_1+{\mathit{\omega }}^{\mathit{\omega }}$ , we provide a sharp bound on the height of the finite word α-automatic well-founded order forests.

∙ For every ordinal $\mathit{\alpha }\mathrm{<}{\mathit{\omega }}_1+{\mathit{\omega }}^{\mathit{\omega }}$ , we provide a structure ${\mathfrak{F}}_{\mathit{\alpha }}$ 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.