Artykuł w czasopiśmie
Brak miniatury
Licencja

ClosedAccessDostęp zamknięty

Measure properties of regular sets of trees

Autor
Mio, Matteo
Gogacz, Tomasz
Skrzypczak, Michał
Michalewski, Henryk
Data publikacji
2017
Abstrakt (EN)

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 ranks. We also expose a connection between regular sets and the σ-algebra of -sets, introduced by A. Kolmogorov in 1928 as a foundation for measure theory. We show that the game tree languages are Wadge-complete for the finite levels of the hierarchy of -sets. We apply these results to answer positively an open problem regarding the game interpretation of the probabilistic μ-calculus.

Słowa kluczowe EN
Regular tree languages
Measure theory
Topological complexity
Dyscyplina PBN
informatyka
Czasopismo
Information and Computation
Tom
256
Strony od-do
108-130
ISSN
0890-5401
Licencja otwartego dostępu
Dostęp zamknięty