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