The complexity of index sets of classes of computably enumerable equivalence relations

DOI10.1017/JSL.2016.26MaRDI QIDQ2976337zbMATH OpenOpenAlexFDO

Authors Uri Andrews, Andrea Sorbi

Publication date 28 April 2017

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1d468be032e7585ebbe61a483f67e6e7dd40e5b1

zbMATH Keywords

computably enumerable equivalence relationcomputable reducibility on equivalence relations

Mathematics Subject Classification ID

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

Recommendations

• Weakly precomplete computably enumerable equivalence relations
• Weakly precomplete equivalence relations in the Ershov hierarchy
• Universal computably enumerable equivalence relations
• On isomorphism classes of computably enumerable equivalence relations
• On the degree structure of equivalence relations under computable reducibility

Cites work

• A Note on Positive Equivalence Relations
• Classical recursion theory. Vol. II
• Computably enumerable equivalence relations
• Graphs realised by r.e. equivalence relations
• Periodicity in generations of automata
• Reducibilities among equivalence relations induced by recursively enumerable structures

Cited in

(11)

• Two results on complexities of decision problems of groups
• Complexity of equivalence relations and preorders from computability theory
• Subrecursive equivalence relations and (non-)closure under lattice operations
• On dark computably enumerable equivalence relations
• On isomorphism classes of computably enumerable equivalence relations
• A survey on universal computably enumerable equivalence relations
• The number of nonequivalent computable indexations for a fixed family of sets
• Index sets for classes of positive preorders
• Weakly precomplete computably enumerable equivalence relations
• On Index Sets of Some Properties of Computable Algebras
• scientific article; zbMATH DE number 892081 (Why is no real title available?)

This page was built for publication: The complexity of index sets of classes of computably enumerable equivalence relations

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