Matteo Mio

I&C Journal 2017 Journal Article

Measure properties of regular sets of trees

• Tomasz Gogacz
• Henryk Michalewski
• Matteo Mio
• Michał Skrzypczak

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 W i, 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.

FLAP Journal 2017 Journal Article

Regular Languages of Infinite Trees and Probability.

• Matteo Mio

Highlights Conference 2015 Conference Abstract

Regular sets of Trees and Probablity

• Matteo Mio

T. Gogacz, H. Michalewski, M. Mio, M. Skrzypczak, "Measure Properties of Game Tree Languages", proc. of MFCS 2014. 2) Regular sets of trees are closed under "small/large projection" with Baire-category interpretation. This implies decidability of the finite-SAT problem of probabilistic logics such as qualitative pCTL*. H. Michalewski, M. Mio, "Baire Category Quantifier in Monadic Second Order Logic", proc. of ICALP 2015. 3) The problem of computing the probability (i. e. , coin-flipping measure) of regular sets of trees definable by game automata is decidable. not yet published. 11: 04 11: 30 Coffee Break

Highlights Conference 2013 Conference Abstract

Game semantics for probabilistic mu-calculi

• Matteo Mio

I will introduce a novel class of two-player games, called "Two-Player Stochastic meta-Parity Games", which are used in my PhD Thesis to give Game Semantics to expressive probabilistic-variants of the Modal mu-Calculus. This new class of games is proven to be "determined". I will discuss some of the technical aspects of the proof.