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 structurescompleteness in the arithmetical hierarchyisomorphism problemrecursion-theoretic complexity

Mathematics Subject Classification ID

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

Review text

In this paper, the authors study the isomorphism problem on classes of automatic structures (finitely presented structures where the universe and all relations can be recognized by finite automata). They prove that the isomorphism problem for automatic equivalence structures is \(\Pi_1^0\)-complete; the isomorphism problem for automatic order trees and linear orders is \(\Sigma_1^1\)-complete; the isomorphism problem for automatic well-founded order trees and automatic trees of bounded height is recursively equivalent to first-order arithmetic; the isomorphism problem for automatic trees of height \(n\geq 2\) is \(\Pi_{2n-3}^0\)-complete. The authors also show that the isomorphism problem for scattered linear orders can be reduced to true arithmetic, but leave open the question on the lower bound for this problem.

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

• 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 of bounded degree revisited
• Automatic Structures: Richness and Limitations
• 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
• 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?)
• 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
• Some natural decision problems in automatic graphs
• STACS 2004
• 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

(22)

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

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)