Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Traceable Sets

Abstract : We investigate systematically into the various possible notions of traceable sets and the relations they bear to each other and to other notions such as diagonally noncomputable sets or complex and autocomplex sets. We review known notions and results that appear in the literature in different contexts, put them into perspective and provide simplified or at least more direct proofs. In addition, we introduce notions of traceability and complexity such as infinitely often versions of jump traceability and of complexity, and derive results about these notions that partially can be viewed as a natural completion of the previously known results. Finally, we give a result about polynomial-time bounded notions of traceability and complexity that shows that in principle the equivalences derived so far can be transferred to the time-bounded setting.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, August 6, 2014 - 4:24:55 PM
Last modification on : Wednesday, August 9, 2017 - 12:03:07 PM
Long-term archiving on: : Wednesday, November 26, 2014 - 12:57:51 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Rupert Hölzl, Wolfgang Merkle. Traceable Sets. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. pp.301-315, ⟨10.1007/978-3-642-15240-5_22⟩. ⟨hal-01054451⟩



Record views


Files downloads