Model Theoretic Complexity of Automatic Structures (Extended Abstract)

DOI10.1007/978-3-540-79228-4_45zbMath1140.03310MaRDI 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

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

03C57: Computable structure theory, computable model theory

03D45: Theory of numerations, effectively presented structures

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, The isomorphism problem on classes of automatic structures with transitive relations, Analysing Complexity in Classes of Unary Automatic Structures

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