Model Theoretic Complexity of Automatic Structures (Extended Abstract)

DOI10.1007/978-3-540-79228-4_45zbMath1140.03310OpenAlexW1487632266MaRDI QIDQ3502675

Mia Minnes, Bakhadyr Khoussainov

Publication date: 27 May 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79228-4_45

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09 ⋮ Deciding the isomorphism problem in classes of unary automatic structures ⋮ Analysing Complexity in Classes of Unary Automatic Structures ⋮ The isomorphism problem on classes of automatic structures with transitive relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On direct products of automaton decidable theories
• Automaticity of ordinals and of homogeneous graphs
• Automatic structures
• Weak Second‐Order Arithmetic and Finite Automata
• Automatic linear orders and trees
• Database Theory - ICDT 2005
• Computable trees of Scott rank ω₁^CK, and computable approximation
• Recursive Pseudo-Well-Orderings
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Logical Reversibility of Computation