Automata on ordinals and automaticity of linear orders (Q1944328)

The following generalization of recognition by finite-state automata is studied: the input tape has the order structure of a limit ordinal. At limits, the states that appeared unboundedly often before the limit, are mapped to a limit state. There is a limit transition function \(P(S) \rightarrow S\). A proof method for non-automaticity of orders is based on analysing ranks defined relatively to the iteration of a finite condensation function. (This function kills scattered intervals). The method is strong enough to prove for example that \(\omega^{\omega^n}\) is the supremum of the \(\omega^n\)-automatic ordinals.