Model-theoretic complexity of automatic structures

DOI10.1016/J.APAL.2009.07.012MaRDI QIDQ636281zbMATH OpenOpenAlexFDO

Authors Bakhadyr Khoussainov, Mia Minnes

Publication date 26 August 2011

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0809.3425, http://hdl.handle.net/1721.1/96326

zbMATH Keywords

automatic structuresisomorphism problemScott rankCantor-Bendixson rankordinal height

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57)

Abstract: We study the complexity of automatic structures via well-established concepts from both logic and model theory, including ordinal heights (of well-founded relations), Scott ranks of structures, and Cantor-Bendixson ranks (of trees). We prove the following results: 1) The ordinal height of any automatic well- founded partial order is bounded by omega^omega ; 2) The ordinal heights of automatic well-founded relations are unbounded below the first non-computable ordinal; 3) For any computable ordinal there is an automatic structure of Scott rank at least that ordinal. Moreover, there are automatic structures of Scott rank the first non-computable ordinal and its successor; 4) For any computable ordinal, there is an automatic successor tree of Cantor-Bendixson rank that ordinal.

Recommendations

• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Scott rank of automatic partial orders
• Structures without scattered-automatic presentation
• Automatic linear orders and trees
• Tree-automatic well-founded trees

Cites work

• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 1302870 (Why is no real title available?)
• scientific article; zbMATH DE number 2047478 (Why is no real title available?)
• scientific article; zbMATH DE number 1405578 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3266609 (Why is no real title available?)
• Automatic linear orders and trees
• Automaticity of ordinals and of homogeneous graphs
• Computable structures of Scott rank \(\omega_1^{CK}\) in familiar classes
• Database Theory - ICDT 2005
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Logical Reversibility of Computation
• On direct products of automaton decidable theories
• Recursive Pseudo-Well-Orderings
• STACS 2004
• The Complexity of Orbits of Computably Enumerable Sets
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(19)

• scientific article; zbMATH DE number 1954377 (Why is no real title available?)
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Automatic structures of bounded degree
• Tree-automatic scattered linear orders
• Pumping for ordinal-automatic structures1
• Scott rank of automatic partial orders
• Complexity and categoricity of injection structures induced by finite state transducers
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Automaticity of ordinals and of homogeneous graphs
• Structures without scattered-automatic presentation
• Generalising automaticity to modal properties of finite structures
• The isomorphism problem for FST injection structures
• From automatic structures to automatic groups.
• Tree-automatic well-founded trees
• Automatic structures of bounded degree revisited
• scientific article; zbMATH DE number 5041651 (Why is no real title available?)
• scientific article; zbMATH DE number 6819808 (Why is no real title available?)
• Advice Automatic Structures and Uniformly Automatic Classes
• Automatic models of first order theories

This page was built for publication: Model-theoretic complexity of automatic structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q636281)