Model Theoretic Complexity of Automatic Structures

2008/09/19 by Bakhadyr Khoussainov, Khoussainov, Bakhadyr, Mia Minnes +1
Computer Science · #03D05 #68Q45 #68Q70 #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.0809.3425

openalex publication_date 2008/09/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 ω^ω; 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.

Related

• The structural complexity of models of arithmetic
• The Rank of Tree-Automatic Linear Orderings
• Structures in Familiar Classes Which Have Scott Rank ω₁^CK
• Scott ranks of models of a theory
• Structures Without Scattered-Automatic Presentation