The isomorphism problem on classes of automatic structures with transitive relations

DOI10.1090/S0002-9947-2013-05766-2zbMath1308.03049MaRDI QIDQ2847190

Jiamou Liu, Markus Lohrey, Dietrich Kuske

Publication date: 4 September 2013

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

isomorphism problemautomatic structuresrecursion-theoretic complexitycompleteness in the arithmetical hierarchy

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

Tree-automatic scattered linear orders, Pumping for ordinal-automatic structures1, Second-order finite automata: expressive power and simple proofs using automatic structures, The isomorphism problem for FST injection structures, Word automatic groups of nilpotency class 2, Effective categoricity of automatic equivalence and nested equivalence structures, Isomorphisms of scattered automatic linear orders, On automaton presentations of projective planes, Tree-Automatic Well-Founded Trees, Classifications of definable subsets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the valuedness of finite transducers
• On direct products of automaton decidable theories
• Handbook of recursive mathematics. Vol. 1: Recursive model theory
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• Computable structures and the hyperarithmetical hierarchy
• Finite presentations of infinite structures: Automata and interpretations
• Automaticity of ordinals and of homogeneous graphs
• An undecidable property of context-free linear orders
• Effective categoricity of equivalence structures
• Isomorphism of Regular Trees and Words
• ALGEBRAIC LINEAR ORDERINGS
• Where Automatic Structures Benefit from Weighted Automata
• The additive group of the rationals does not have an automatic presentation
• Automatic structures of bounded degree revisited
• BREAKING UP FINITE AUTOMATA PRESENTABLE TORSION-FREE ABELIAN GROUPS
• Classification from a Computable Viewpoint
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• Automata Presenting Structures: A Survey of the Finite String Case
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• Describing Groups
• Some natural decision problems in automatic graphs
• The Isomorphism Problem for ω-Automatic Trees
• Analysing Complexity in Classes of Unary Automatic Structures
• On frontiers of regular trees
• Decision Problems of Finite Automata Design and Related Arithmetics
• Isomorphisms of scattered automatic linear orders.
• STACS 2004
• Automatic Structures: Richness and Limitations
• Computable trees of Scott rank ω₁^CK, and computable approximation
• Tree-Automatic Well-Founded Trees