Computably Enumerable Equivalence Relations
arXiv:1012.0944 · doi:10.1023/A:1010521410739
Abstract
We study computably enumerable equivalence relations (ceers) on N and unravel a rich structural theory for a strong notion of reducibility among ceers.
Cited by in corpus (13)
- The hierarchy of equivalence relations on the natural numbers under computable reducibility
- On the structure of computable reducibility on equivalence relations of natural numbers
- Classifying equivalence relations in the Ershov hierarchy
- Punctual equivalence relations and their (punctual) complexity
- Measuring the complexity of reductions between equivalence relations
- Computable Component-wise Reducibility
- Computably discrete represented spaces
- Complexity of equivalence relations and preorders from computability theory
- Computable reducibility of equivalence relations and an effective jump operator
- Calibrating word problems of groups via the complexity of equivalence relations
- Comparing the isomorphism types of equivalence structures and preorders
- Semi-decidable equivalence relations obtained by composition and lattice join of decidable equivalence relations
- Word problems and ceers