Reductions between types of numberings

Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.apal.2019.102716

Title:	Reductions between types of numberings
Authors:	Herbert I. Jain S. Lempp S. Mustafa M. Stephan F.
Keywords:	n-r.e. sets Ordinals in recursion theory Recursively enumerable sets Reducibilities between numberings Theory of numberings in the difference hierarchy
Issue Date:	2019
Publisher:	Elsevier B.V.
Citation:	Herbert I., Jain S., Lempp S., Mustafa M., Stephan F. (2019). Reductions between types of numberings. Annals of Pure and Applied Logic 170 (12) : 102716. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2019.102716
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 to use these reductions to simplify some constructions of specific semilattices. 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. © 2019 Elsevier B.V.
Source Title:	Annals of Pure and Applied Logic
URI:	https://scholarbank.nus.edu.sg/handle/10635/177519
ISSN:	0168-0072
DOI:	10.1016/j.apal.2019.102716
Appears in Collections:	Staff Publications Elements

File	Description	Size	Format	Access Settings	Version
reductionsbetweentypes.pdf		313.46 kB	Adobe PDF	OPEN	Post-print	View/Download

Check