The Rank of Tree-Automatic Linear Orderings

2012/04/13 by Martin Huschenbett, Huschenbett, Martin
Computer Science · #Advanced Graph Theory Research #Computability, Logic, AI Algorithms #F.4.1 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1204.3048

openalex publication_date 2012/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We generalise Delhommé's result that each tree-automatic ordinal is strictly below ω^ωω by showing that any tree-automatic linear ordering has FC-rank strictly below ω^ω. We further investigate a restricted form of tree-automaticity and prove that every linear ordering which admits a tree-automatic presentation of branching complexity at most k has FC-rank strictly below ω^k.

Related

• Model Theoretic Complexity of Automatic Structures
• Algebraic Linear Orderings
• Structures Without Scattered-Automatic Presentation
• Generically Computable Linear Orderings
• Rankability and Linear Ordering Problem: New Probabilistic Insight and Algorithms