A Survey on Universal Computably Enumerable Equivalence Relations

DOI10.1007/978-3-319-50062-1_25zbMath1485.03146MaRDI QIDQ2970971

S. A. Badaev, Andrea Sorbi, Uri Andrews

Publication date: 4 April 2017

Published in: Computability and Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-50062-1_25

zbMATH Keywords

computably enumerable equivalence relation; computable reducibility on equivalence relations

Mathematics Subject Classification ID

03D25: Recursively (computably) enumerable sets and degrees

Related Items

On dark computably enumerable equivalence relations, Elementary theories and hereditary undecidability for semilattices of numberings, Weakly precomplete equivalence relations in the Ershov hierarchy, Fixed point theorems for precomplete numberings, Boolean algebras realized by c.e. equivalence relations

Cites Work

• Unnamed Item
• Unnamed Item
• On weakly pre-complete positive equivalences
• Reducibilities among equivalence relations induced by recursively enumerable structures
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Relatively precomplete numerations and arithmetic
• Positive equivalences
• Graphs realised by r.e. equivalence relations
• Weakly precomplete computably enumerable equivalence relations
• Equivalence Relations That Are $\Sigma^0_3$ Complete for Computable Reducibility
• UNIVERSAL COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• THE COMPLEXITY OF INDEX SETS OF CLASSES OF COMPUTABLY ENUMERABLE EQUIVALENCE RELATIONS
• A Note on Positive Equivalence Relations
• LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS
• Theory of Formal Systems. (AM-47)
• Creative Functions
• Classifying positive equivalence relations
• Equivalence relations induced by extensional formulae: classification by means of a new fixed point property
• Theorie der Numerierungen I
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Remarks on Uniformly Finitely Precomplete Positive Equivalences
• The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
• Isomorphism relations on computable structures
• Creative sets
• Computably enumerable equivalence relations