Equivalence relations that are ^0_3 complete for computable reducibility (extended abstract)

DOI10.1007/978-3-642-32621-9_2MaRDI QIDQ2915014zbMATH OpenOpenAlexFDO

Authors E. B. Fokina, André Nies, Sy-David Friedman

Publication date 21 September 2012

Published in Logic, Language, Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32621-9_2

zbMATH Keywords

computable structuresinvariant descriptive set theory

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Descriptive set theory (03E15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On the degree structure of equivalence relations under computable reducibility
• Finitary reducibility on equivalence relations
• Complexity of equivalence relations and preorders from computability theory
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Isomorphism relations on computable structures

Cited in

(17)

• Finitary reducibility on equivalence relations
• Enumerating classes of effective quasi-Polish spaces
• Complexity of equivalence relations and preorders from computability theory
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Computable embeddability for algebraic structures
• Isomorphism relations on computable structures
• On polynomial-time relation reducibility
• A survey on universal computably enumerable equivalence relations
• Weakly precomplete computably enumerable equivalence relations
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Completeness of the hyperarithmetic isomorphism equivalence relation
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• ISOMORPHISM ON HYP
• Jumps of computably enumerable equivalence relations
• On the degree structure of equivalence relations under computable reducibility
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies

This page was built for publication: Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)

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