Abstract
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 language | English |
|---|---|
| Pages (from-to) | 1-30 |
| Number of pages | 30 |
| Journal | Annals of Pure and Applied Logic |
| DOIs | |
| Publication status | Published - Jul 4 2019 |
Fingerprint
Cite this
Reductions between types of numberings. / Herbert, Ian; Jain, Sanjay; Lempp, Steffen; Mustafa, Manat; Stephan, Frank.
In: Annals of Pure and Applied Logic, 04.07.2019, p. 1-30.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Reductions between types of numberings
AU - Herbert, Ian
AU - Jain, Sanjay
AU - Lempp, Steffen
AU - Mustafa, Manat
AU - Stephan, Frank
PY - 2019/7/4
Y1 - 2019/7/4
N2 - This paper considers reductions between types of numberings; these reductionspreserve the Rogers Semilattice of the numberings reduced and also preservethe 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.
AB - This paper considers reductions between types of numberings; these reductionspreserve the Rogers Semilattice of the numberings reduced and also preservethe 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.
U2 - https://doi.org/10.1016/j.apal.2019.102716
DO - https://doi.org/10.1016/j.apal.2019.102716
M3 - Article
SP - 1
EP - 30
JO - Annals of Pure and Applied Logic
JF - Annals of Pure and Applied Logic
SN - 0168-0072
ER -