Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-38236-9_14
DC FieldValue
dc.titleSelection by recursively enumerable sets
dc.contributor.authorMerkle, W.
dc.contributor.authorStephan, F.
dc.contributor.authorTeutsch, J.
dc.contributor.authorWang, W.
dc.contributor.authorYang, Y.
dc.date.accessioned2014-10-28T02:51:44Z
dc.date.available2014-10-28T02:51:44Z
dc.date.issued2013
dc.identifier.citationMerkle, W.,Stephan, F.,Teutsch, J.,Wang, W.,Yang, Y. (2013). Selection by recursively enumerable sets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7876 LNCS : 144-155. ScholarBank@NUS Repository. <a href="https://doi.org/10.1007/978-3-642-38236-9_14" target="_blank">https://doi.org/10.1007/978-3-642-38236-9_14</a>
dc.identifier.isbn9783642382352
dc.identifier.issn16113349
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/104624
dc.description.abstractFor given sets A, B and Z of natural numbers where the members of Z are z0, z1,⋯ in ascending order, one says that A is selected from B by Z if A(i) = B(zi) for all i. Furthermore, say that A is selected from B if A is selected from B by some recursively enumerable set, and that A is selected from B in n steps iff there are sets E0, E1,⋯, En such that E0 = A, En = B, and Ei is selected from Ei+1 for each i < n. The following results on selections are obtained in the present paper. A set is ω-r.e. if and only if it can be selected from a recursive set in finitely many steps if and only if it can be selected from a recursive set in two steps. There is some Martin-Löf random set from which any ω-r.e. set can be selected in at most two steps, whereas no recursive set can be selected from a Martin-Löf random set in one step. Moreover, all sets selected from Chaitin's Ω in finitely many steps are Martin-Löf random. © Springer-Verlag Berlin Heidelberg 2013.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/978-3-642-38236-9_14
dc.sourceScopus
dc.typeConference Paper
dc.contributor.departmentMATHEMATICS
dc.description.doi10.1007/978-3-642-38236-9_14
dc.description.sourcetitleLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.description.volume7876 LNCS
dc.description.page144-155
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

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

Page view(s)

88
checked on Jan 27, 2022

Google ScholarTM

Check

Altmetric


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