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.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 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. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.301-315, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_22〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054451
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:55
Dernière modification le : mercredi 9 août 2017 - 12:03:07
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:57:51

Fichier

03230301.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Rupert Hölzl, Wolfgang Merkle. Traceable Sets. Cristian S. Calude; Vladimiro Sassone. 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. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.301-315, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_22〉. 〈hal-01054451〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

75