Effective categoricity of automatic equivalence and nested equivalence structures

DOI10.1007/S00224-020-09974-9MaRDI QIDQ2195573zbMATH OpenOpenAlexFDO

Authors J. Carson, Douglas Cenzer, Jeffrey Remmel

Publication date 26 August 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-020-09974-9

zbMATH Keywords

automatic structurescomputable structureseffective categoricityequivalence structuresnested equivalence structuresonline structures

Mathematics Subject Classification ID

Categoricity and completeness of theories (03C35) Computable structure theory, computable model theory (03C57)

Recommendations

• Effective categoricity of equivalence structures
• Equivalence structures and isomorphisms in the difference hierarchy
• The isomorphism problem on classes of automatic structures with transitive relations
• ^0_2-categoricity of equivalence structures
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures

Cites work

• ^0_2-categoricity of equivalence structures
• Atomless Boolean algebras computable in polynomial time
• Automata theory and its applications
• AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
• Automatic Equivalence Structures of Polynomial Growth.
• Automatic Structures: Richness and Limitations
• Automaticity of ordinals and of homogeneous graphs
• Categoricity for primitive recursive and polynomial Boolean algebras
• Complexity and categoricity
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Deciding the isomorphism problem in classes of unary automatic structures
• Effective categoricity of equivalence structures
• Existence and uniqueness of structures computable in polynomial time
• Finite-State Processes and Dynamic Programming
• FOUNDATIONS OF ONLINE STRUCTURE THEORY
• Generic copies of countable structures
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 5605134 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1747445 (Why is no real title available?)
• Injection Structures Specified by Finite State Transducers
• On direct products of automaton decidable theories
• Structures computable in polynomial time. I
• Structures computable in polynomial time. II
• The back-and-forth method and computability without delay
• The isomorphism problem on classes of automatic structures with transitive relations
• Three lectures on automatic structures
• Unary automatic graphs: an algorithmic perspective
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(5)

• Complexity and categoricity of injection structures induced by finite state transducers
• Degrees of bi-embeddable categoricity of equivalence structures
• Effective categoricity of equivalence structures
• ^0_2-categoricity of equivalence structures
• Equivalence structures and isomorphisms in the difference hierarchy

This page was built for publication: Effective categoricity of automatic equivalence and nested equivalence structures

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