Automata on ordinals and automaticity of linear orders

&
Annals of Pure and Applied Logic 164 (5):523-527 (2013)
  Copy   BIBTEX

Abstract

We investigate structures recognizable by finite state automata with an input tape of length a limit ordinal. At limits, the set of states which appear unboundedly often before the limit are mapped to a limit state. We describe a method for proving non-automaticity and apply this to determine the optimal bounds for the ranks of linear orders recognized by such automata

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2012.11.007

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,130

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

On categoricity of scattered linear orders of constructive ranks.Andrey Frolov & Maxim Zubkov - forthcoming - Archive for Mathematical Logic:1-19.
Linear logic automata.Max I. Kanovich - 1996 - Annals of Pure and Applied Logic 78 (1-3):147-188.
On Relation Between Linear Temporal Logic and Quantum Finite Automata.Amandeep Singh Bhatia & Ajay Kumar - 2020 - Journal of Logic, Language and Information 29 (2):109-120.
Alternating automata and temporal logic normal forms.Clare Dixon, Alexander Bolotov & Michael Fisher - 2005 - Annals of Pure and Applied Logic 135 (1-3):263-285.
Deterministic automata simulation, universality and minimality.Cristian Calude, Elena Calude & Bakhadyr Khoussainov - 1997 - Annals of Pure and Applied Logic 90 (1-3):263-276.
Finite State Automata and Monadic Definability of Singular Cardinals.Itay Neeman - 2008 - Journal of Symbolic Logic 73 (2):412 - 438.
Verification of concurrent programs: the automata-theoretic framework.Moshe Y. Vardi - 1991 - Annals of Pure and Applied Logic 51 (1-2):79-98.
Scott Sentence Complexities of Linear Orderings.David Gonzalez & Dino Rossegger - forthcoming - Journal of Symbolic Logic:1-30.
Infinite games specified by 2-tape automata.Olivier Finkel - 2016 - Annals of Pure and Applied Logic 167 (12):1184-1212.
On Fraïssé’s conjecture for linear orders of finite Hausdorff rank.Alberto Marcone & Antonio Montalbán - 2009 - Annals of Pure and Applied Logic 160 (3):355-367.

Analytics

Added to PP
2013-12-12

Downloads
53 (#407,997)

6 months
5 (#1,035,700)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references