A Survey on Universal Computably Enumerable Equivalence Relations

DOI10.1007/978-3-319-50062-1_25zbMath1485.03146OpenAlexW2558071339MaRDI 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 relationcomputable reducibility on equivalence relations

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Related Items

Special classes of positive preorders ⋮ On dark computably enumerable equivalence relations ⋮ Primitive recursive equivalence relations and their primitive recursive complexity ⋮ Partial combinatory algebra and generalized numberings ⋮ Fixpoints and relative precompleteness ⋮ Index sets for classes of positive preorders ⋮ Boolean algebras realized by c.e. equivalence relations ⋮ INITIAL SEGMENTS OF THE DEGREES OF CEERS ⋮ Numberings, c.e. oracles, and fixed points ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Word problems and ceers ⋮ Classifying word problems of finitely generated algebras via computable reducibility ⋮ On universal positive graphs ⋮ Computable reducibility for computable linear orders of type \(\omega \) ⋮ Classifying equivalence relations in the Ershov hierarchy ⋮ Minimal equivalence relations in hyperarithmetical and analytical hierarchies ⋮ The structure of computably enumerable preorder relations ⋮ Elementary theories and hereditary undecidability for semilattices of numberings ⋮ Weakly precomplete equivalence relations in the Ershov hierarchy ⋮ Fixed point theorems for precomplete numberings ⋮ The category of equivalence relations ⋮ Well-orders realized by C.E. equivalence relations ⋮ EFFECTIVE INSEPARABILITY, LATTICES, AND PREORDERING RELATIONS ⋮ Computable embeddability for algebraic structures ⋮ Subrecursive equivalence relations and (non-)closure under lattice operations

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