EUVIMEDEUVIMED entdecken
Crossref

The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility

Samuel Coskey, Joel David Hamkins, Russell Miller

Computability · 2012 · 1 (1) · 15-38

DOI: 10.3233/com-2012-004 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Computability, 2012. Verfasst von Samuel Coskey und 2 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility. We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel reducibility hierarchy from descriptive set theory. Meanwhile, the notion of computable reducibility appears well suited for an analysis of equivalence relations on the c.e. sets, and more specifically, on various classes of c.e. structures. This is a rich context with many natural examples, such as the isomorphism relation on c.e. graphs or on computably presented groups. Here, our exposition extends earlier work in the literature concerning the classification of computable structures. An abundance of open questions remains.

Zitieren

APA

Coskey, S., Hamkins, J. D., & Miller, R. (2012). The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility. Computability, 1(1), 15-38. https://doi.org/10.3233/com-2012-004

Vancouver

Coskey S, Hamkins JD, Miller R. The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility. Computability. 2012;1(1):15-38. doi:10.3233/com-2012-004

BibTeX
@article{Coskey2012,
  author = {Coskey, Samuel and Hamkins, Joel David and Miller, Russell},
  title = {The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility},
  journal = {Computability},
  year = {2012},
  volume = {1},
  number = {1},
  pages = {15--38},
  doi = {10.3233/com-2012-004}
}
Kostenlos starten →