The isomorphism problem on classes of automatic structures with transitive relations
From MaRDI portal
Publication:2847190
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)
isomorphism problem; automatic structures; recursion-theoretic complexity; completeness in the arithmetical hierarchy
03D05: Automata and formal grammars in connection with logical questions
03C57: Computable structure theory, computable model theory
03D45: Theory of numerations, effectively presented structures
Related Items
Pumping for ordinal-automatic structures1, Tree-Automatic Well-Founded Trees, Word automatic groups of nilpotency class 2, Tree-automatic scattered linear orders, On automaton presentations of projective planes, Second-order finite automata: expressive power and simple proofs using automatic structures, The isomorphism problem for FST injection structures, Effective categoricity of automatic equivalence and nested equivalence structures, Classifications of definable subsets, Isomorphisms of scattered automatic linear orders
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 ω1CK, and computable approximation
- Tree-Automatic Well-Founded Trees
