A survey on universal computably enumerable equivalence relations

DOI10.1007/978-3-319-50062-1_25zbMATH Open1485.03146OpenAlexW2558071339MaRDI QIDQ2970971FDOQ2970971

Authors Uri Andrews, Serikzhan A. Badaev, Andrea Sorbi 

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)

Recommendations

• Universal computably enumerable equivalence relations
• Weakly precomplete computably enumerable equivalence relations
• The theory of ceers computes true arithmetic
• On isomorphism classes of computably enumerable equivalence relations
• Jumps of computably enumerable equivalence relations

Cites work

• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A Note on Positive Equivalence Relations
• Classifying positive equivalence relations
• Computability theory
• Computably enumerable equivalence relations
• Creative Functions
• Creative sets
• Equivalence relations induced by extensional formulae: classification by means of a new fixed point property
• Equivalence relations that are \(\Sigma^0_3\) complete for computable reducibility (extended abstract)
• Graphs realised by r.e. equivalence relations
• Isomorphism relations on computable structures
• Linear orders realized by c.e. equivalence relations
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• On the relation provable equivalence and on partitions in effectively inseparable sets
• On weakly pre-complete positive equivalences
• Positive equivalences
• Reducibilities among equivalence relations induced by recursively enumerable structures
• Relatively precomplete numerations and arithmetic
• Remarks on Uniformly Finitely Precomplete Positive Equivalences
• The complexity of index sets of classes of computably enumerable equivalence relations
• The hierarchy of equivalence relations on the natural numbers under computable reducibility
• Theorie der Numerierungen I
• Theory of Formal Systems. (AM-47)
• Universal computably enumerable equivalence relations
• Weakly precomplete computably enumerable equivalence relations

Cited in

(29)

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

This page was built for publication: A survey on universal computably enumerable equivalence relations

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