Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950579 | Information and Computation | 2017 | 23 Pages |
Abstract
We investigate measure theoretic properties of regular sets of infinite trees. As a first result, we prove that every regular set is universally measurable and that every Borel measure on the Polish space of trees is continuous with respect to a natural transfinite stratification of regular sets into Ï1 ranks. We also expose a connection between regular sets and the Ï-algebra of R-sets, introduced by A. Kolmogorov in 1928 as a foundation for measure theory. We show that the game tree languages Wi,k are Wadge-complete for the finite levels of the hierarchy of R-sets. We apply these results to answer positively an open problem regarding the game interpretation of the probabilistic μ-calculus.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tomasz Gogacz, Henryk Michalewski, Matteo Mio, MichaÅ Skrzypczak,