The isomorphism problem on classes of automatic structures with transitive relations

DOI10.1090/S0002-9947-2013-05766-2MaRDI QIDQ2847190zbMATH OpenFDO

Authors Jiamou Liu, Markus Lohrey, Dietrich Kuske

Publication date 4 September 2013

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

Full work available at URL https://doi.org/10.1090/S0002-9947-2013-05766-2

zbMATH Keywords

automatic structuresisomorphism problemrecursion-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)

Recommendations

• scientific article; zbMATH DE number 5041651
• The isomorphism relation between tree-automatic structures
• The isomorphism problem for \(\omega \)-automatic trees
• Deciding the isomorphism problem in classes of unary automatic structures
• The isomorphism problem for \(\omega \)-automatic trees

Cites work

• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 53151 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 1499098 (Why is no real title available?)
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• Algebraic linear orderings
• An undecidable property of context-free linear orders
• Analysing Complexity in Classes of Unary Automatic Structures
• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic Structures: Richness and Limitations
• Automatic structures of bounded degree revisited
• Automaticity of ordinals and of homogeneous graphs
• Breaking up finite automata presentable torsion-free Abelian groups.
• Cardinality and counting quantifiers on omega-automatic structures
• Classification from a Computable Viewpoint
• Computable structures and the hyperarithmetical hierarchy
• Computable trees of Scott rank ω₁^CK, and computable approximation
• Decision Problems of Finite Automata Design and Related Arithmetics
• Describing Groups
• Effective categoricity of equivalence structures
• Ehrenfeucht-Fraïssé goes elementarily automatic for structures of bounded degree
• Finite presentations of infinite structures: Automata and interpretations
• Handbook of recursive mathematics. Vol. 1: Recursive model theory
• Isomorphism of regular trees and words
• Isomorphisms of scattered automatic linear orders
• Model Theoretic Complexity of Automatic Structures (Extended Abstract)
• On direct products of automaton decidable theories
• On frontiers of regular trees
• On the problem whether the image of an N-rational series equals N
• On the valuedness of finite transducers
• Realizing levels of the hyperarithmetic hierarchy as degree spectra of relations on computable structures
• STACS 2004
• Some natural decision problems in automatic graphs
• The additive group of the rationals does not have an automatic presentation
• The isomorphism problem for \(\omega \)-automatic trees
• Tree-automatic well-founded trees
• Where automatic structures benefit from weighted automata

Cited in

(21)

• scientific article; zbMATH DE number 1396671 (Why is no real title available?)
• Tree-automatic scattered linear orders
• Second-order finite automata: expressive power and simple proofs using automatic structures
• Pumping for ordinal-automatic structures1
• Automatic Structures: Richness and Limitations
• A hierarchy of tree-automatic structures
• The isomorphism relation between tree-automatic structures
• Effective categoricity of automatic equivalence and nested equivalence structures
• The isomorphism problem for \(\omega \)-automatic trees
• The isomorphism problem for \(\omega \)-automatic trees
• Deciding the isomorphism problem in classes of unary automatic structures
• Analysing Complexity in Classes of Unary Automatic Structures
• The isomorphism problem for FST injection structures
• Word automatic groups of nilpotency class 2
• On automaton presentations of projective planes
• Isomorphisms of scattered automatic linear orders
• The isomorphism problem for tree-automatic ordinals with addition
• Tree-automatic well-founded trees
• Isomorphisms of scattered automatic linear orders
• Isomorphism of regular trees and words
• Classifications of definable subsets

This page was built for publication: The isomorphism problem on classes of automatic structures with transitive relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2847190)