Computability in the Lattice of Equivalence Relations

Jean-Yves Moyen
(University of Copenhagen)
Jakob Grue Simonsen
(University of Copenhagen)

We investigate computability in the lattice of equivalence relations on the natural numbers. We mostly investigate whether the subsets of appropriately defined subrecursive equivalence relations -for example the set of all polynomial-time decidable equivalence relations- form sublattices of the lattice.

In Guillaume Bonfante and Georg Moser: Proceedings 8th Workshop on Developments in Implicit Computational complExity and 5th Workshop on FOundational and Practical Aspects of Resource Analysis (DICE-FOPARA 2017), Uppsala, Sweden, April 22-23, 2017, Electronic Proceedings in Theoretical Computer Science 248, pp. 38–46.
Published: 18th April 2017.

ArXived at: https://dx.doi.org/10.4204/EPTCS.248.8 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org