History

Please fill in your query. A complete syntax description you will find on the General Help page.
Weak randomness, genericity and Boolean decision trees. (English)
Arai, T. (ed.) et al., Proceedings of the 10th Asian logic conference, Kobe, Japan, September 1‒6, 2008. Hackensack, NJ: World Scientific (ISBN 978-981-4293-01-3/hbk; 978-981-4293-02-0/ebook). 322-344 (2010).
The paper studies the class $\cal D$ of $r$-generic sets in the sense of {\it M. Dowd} [Inf.~Comput.~96, No.~1, 65‒76 (1992; Zbl 0755.68052)]. The following results are given: { indent=6.5mm \item{(a)} $\cal D$ is closed under independent bounded truth-table reductions, that is, bounded truth-table reductions that for different arguments produce disjoint sets of oracle queries and use only Boolean onto functions as truth tables. \item{(b)} (an immediate consequence of the above) $\cal D$ is closed under reductions computed by sequences of Boolean alternating AND-OR circuits (for some reason called Boolean decision trees in the paper). \item{(c)} Every Martin-Löf random sequence is in $\cal D$. However, the class of Martin-Löf random sets (as well as the class of weak Martin-Löf random sets) is not closed under the reductions used in (b) above. }
Reviewer: Heribert Vollmer (Hannover)