Reductions between types of numberings

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

doi:10.1016/j.apal.2019.102716

Reductions between types of numberings

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

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

13 Citations (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 language	English
Pages (from-to)	1-30
Number of pages	30
Journal	Annals of Pure and Applied Logic
DOIs	https://doi.org/10.1016/j.apal.2019.102716
Publication status	Published - Jul 4 2019

Access to Document

10.1016/j.apal.2019.102716Licence: GNU LGPL

Cite this

@article{df18d99319f04f04a517f6f08c9250a7,

title = "Reductions between types of numberings",

abstract = "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.",

author = "Ian Herbert and Sanjay Jain and Steffen Lempp and Manat Mustafa and Frank Stephan",

year = "2019",

month = jul,

day = "4",

doi = "10.1016/j.apal.2019.102716",

language = "English",

pages = "1--30",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier",

}

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 - 10.1016/j.apal.2019.102716

DO - 10.1016/j.apal.2019.102716

M3 - Article

SN - 0168-0072

SP - 1

EP - 30

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

ER -

Reductions between types of numberings

Abstract

Access to Document

Fingerprint

Cite this