The Topological Complexity of Models of the Modal μ-Calculus: On The Alternation Free Fragment and Beyond
Jacques Duparc, Alessandro Facchini · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
Recently Murlak and one of the authors have shown that the family of trees recognized by weak alternating automata (or equivalently, the family of tree models of the alternation free fragment of the modal µ-calculus) is closed under three set theoretic operations that corresponds to sum, multiplication by ordinals < ωω and pseudo exponentiation with the base ω1 of the Wadge degree. Moreover they have conjectured that the height of this hierarchy is exactly ε0. We make a first step towards the proof of this conjecture by showing that there is no set definable by an alternation free µ-formula in between the levels ωω and ω1 of the Wadge Hierarchy of Borel Sets. However, very little is known about the Wadge hierarchy for the full µ-calculus, the problem being that most of the sets definable by a µ-formula are even not Borel. We make a first step in this direction by introducing the Wadge hierarchy extending the one for the alternating free fragment with an action given by a difference of two Π1 1 complete sets.