Automata on ordinals and automaticity of linear orders
type: Item
instance of: scholarly article
title: Automata on ordinals and automaticity of linear orders
zbMATH Open document ID: 1285.03050
author: Philipp Schlicht
author: Frank Stephan
published in: Annals of Pure and Applied Logic
publication date: 2013-04-05T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 6150716
zbMATH Keywords: recognition by finite automata
zbMATH Keywords: infinite input tape
zbMATH Keywords: limit ordinal input tape
zbMATH Keywords: limit transition function
zbMATH Keywords: non-automaticity of linear orders
reviewed by: Mihai Prunescu
MaRDI profile type: Publication
full work available at URL: j.apal.2012.11.007
OpenAlex ID: W2084168663
DOI: 10.1016/J.APAL.2012.11.007
Recommended article: Automata on Ordinals and Linear Orders
Recommended article: Q4779147
Recommended article: Q4412103
Recommended article: Automata on linear orderings
Recommended article: On defining linear orders by automata
Recommended article: Hierarchy among automata on linear orderings
Recommended article: On varieties of ordered automata
Recommended article: On automatic and decidable linear orderings
Recommended article: Finite automata and ordinals
Recommended article: Determinization of ordinal automata
description: scientific article; zbMATH DE number 6150716