Computability in the lattice of equivalence relations

Jean-Yves Moyen, Jakob Grue Simonsen

1 Citation (Scopus)
55 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationProceedings 8th Workshop on Developments in Implicit Computational Complexity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis
EditorsGuillaume Bonfante, Georg Moser
Number of pages9
PublisherOpen Publishing Association
Publication date18 Apr 2017
Pages38-46
DOIs
Publication statusPublished - 18 Apr 2017
Event8th Workshop on Developments in Implicit Computational Complexity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis - Uppsala, Sweden
Duration: 22 Apr 201723 Apr 2017

Workshop

Workshop8th Workshop on Developments in Implicit Computational Complexity and 5th Workshop on Foundational and Practical Aspects of Resource Analysis
Country/TerritorySweden
CityUppsala
Period22/04/201723/04/2017
SeriesElectronic Proceedings in Theoretical Computer Science
Volume248
ISSN2075-2180

Fingerprint

Dive into the research topics of 'Computability in the lattice of equivalence relations'. Together they form a unique fingerprint.

Cite this