| Résume | Monadic Second-order (MSO) logic is a well-studied formalism featuring many decision procedures and effective transformations. It is the fundamental logic considered in automata theory, equivalent to various other ways of defining sets of objects. In this talk, I will speak about the expressive power of MSO over infinite binary trees (i.e. free structures of two successors) - the theory from the famous Rabin's decidability result.
The goal of the talk is to survey recent results about measure properties of MSO-definable sets of infinite trees. First, I will argue that these sets are indeed measurable (which is not obvious, as there exist non-Borel sets definable in MSO). Then I will move to the question of our ability to compute the measure of the set defined by a given formula. Although the general question is still open (and seems to be demanding), I will speak about decidability results for fragments of MSO, focusing on the so-called weak-MSO. |
