Model-theoretic complexity of automatic structures

DOI10.1016/J.APAL.2009.07.012zbMATH Open1221.03025arXiv0809.3425OpenAlexW1523399120MaRDI QIDQ636281FDOQ636281

Authors: Bakhadyr Khoussainov, Mia Minnes 

Publication date: 26 August 2011

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

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.

Full work available at URL: https://arxiv.org/abs/0809.3425

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

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)

Cites Work

• On direct products of automaton decidable theories
• Automaticity of ordinals and of homogeneous graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic linear orders and trees
• STACS 2004
• Title not available (Why is that?)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Logical Reversibility of Computation
• Title not available (Why is that?)
• Weak Second‐Order Arithmetic and Finite Automata
• Title not available (Why is that?)
• Database Theory - ICDT 2005
• Title not available (Why is that?)
• Recursive Pseudo-Well-Orderings
• Title not available (Why is that?)
• Computable structures of Scott rank \(\omega_1^{CK}\) in familiar classes
• The Complexity of Orbits of Computably Enumerable Sets

Cited In (19)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Advice Automatic Structures and Uniformly Automatic Classes
• Automatic models of first order theories
• Title not available (Why is that?)

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)