Model-theoretic complexity of automatic structures

DOI10.1016/j.apal.2009.07.012zbMath1221.03025arXiv0809.3425OpenAlexW1523399120MaRDI QIDQ636281

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

zbMATH Keywords

isomorphism problemautomatic structuresScott 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)

Related Items

Tree-automatic scattered linear orders ⋮ Pumping for ordinal-automatic structures1 ⋮ The isomorphism problem for FST injection structures ⋮ From automatic structures to automatic groups. ⋮ Tree-Automatic Well-Founded Trees ⋮ AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES ⋮ Complexity and categoricity of injection structures induced by finite state transducers

Cites Work

• On direct products of automaton decidable theories
• Automaticity of ordinals and of homogeneous graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Automatic linear orders and trees
• STACS 2004
• Database Theory - ICDT 2005
• The Complexity of Orbits of Computably Enumerable Sets
• Recursive Pseudo-Well-Orderings
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Logical Reversibility of Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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