Reductions between types of numberings

Ian Herbert, Sanjay Jain, Steffen Lempp, Manat Mustafa, Frank Stephan

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

This paper considers reductions between types of numberings; these reductions
preserve the Rogers Semilattice of the numberings reduced and also preserve
the number of minimal and positive degrees in their semilattice. It is shown how these reductions can be used to answer some open problems. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the (k + 1)-r.e. numberings; all further reductions are obtained by concatenating these reductions.
Original languageEnglish
Pages (from-to)1-30
Number of pages30
JournalAnnals of Pure and Applied Logic
DOIs
Publication statusPublished - Jul 4 2019

Fingerprint Dive into the research topics of 'Reductions between types of numberings'. Together they form a unique fingerprint.

  • Cite this