\(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures

DOI10.1016/j.apal.2011.01.002zbMath1241.03040OpenAlexW2054004295MaRDI QIDQ639658

Valentina S. Harizanov, Douglas Cenzer, Jeffery B. Remmel

Publication date: 22 September 2011

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2011.01.002

zbMATH Keywords

computability theorycomputable model theorydecidable structureseffective categoricityequivalence structuresnegative structurespositive structures

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Related Items

Generically and coarsely computable isomorphisms, The isomorphism problem for FST injection structures, Computability theory. Abstracts from the workshop held April 25 -- May 1, 2021 (hybrid meeting), \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures, Effective Categoricity of Injection Structures, On decidability of list structures, Computability-theoretic properties of injection structures, Complexity and categoricity of injection structures induced by finite state transducers

Cites Work

• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• Computable categoricity and the Ershov hierarchy
• Positive equivalences
• Effective categoricity of equivalence structures
• A Note on Positive Equivalence Relations
• Classifying positive equivalence relations
• Equivalence structures and isomorphisms in the difference hierarchy
• Combinational functors on co-r.e. structures
• Recursively enumerable vector spaces
• Recursively Enumerable Equivalence Relations Modulo Finite Differences
• Computably enumerable equivalence relations
• Unnamed Item
• Unnamed Item
• Unnamed Item