Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.entcs.2005.05.025
Title: Lowness properties and approximations of the jump
Authors: Figueira, S.
Nies, A.
Stephan, F. 
Keywords: ω-r.e.
K-triviality
Kolmogorov complexity
Lowness
Traceability
Issue Date: 6-Jan-2006
Citation: Figueira, S., Nies, A., Stephan, F. (2006-01-06). Lowness properties and approximations of the jump. Electronic Notes in Theoretical Computer Science 143 (SPEC. ISS.) : 45-57. ScholarBank@NUS Repository. https://doi.org/10.1016/j.entcs.2005.05.025
Abstract: We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and ω-r.e. for sets of natural numbers. We prove that there is a strongly jump-traceable set which is not computable, and that if A′ is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and the corresponding strong variant in terms of Kolmogorov complexity, and we investigate other properties of these lowness notions. © 2005 Elsevier B.V. All rights reserved.
Source Title: Electronic Notes in Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/104663
ISSN: 15710661
DOI: 10.1016/j.entcs.2005.05.025
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

9
checked on Jun 16, 2018

WEB OF SCIENCETM
Citations

7
checked on May 16, 2018

Page view(s)

49
checked on Jun 8, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.