The Topological Complexity of Models of the Modal μ-Calculus: On The Alternation Free Fragment and Beyond

Details

Serval ID
serval:BIB_977532F15AA6
Type
Report: a report published by a school or other institution, usually numbered within a series.
Publication sub-type
Working paper: Working papers contain results presented by the author. Working papers aim to stimulate discussions between scientists with interested parties, they can also be the basis to publish articles in specialized journals
Collection
Publications
Institution
Title
The Topological Complexity of Models of the Modal μ-Calculus: On The Alternation Free Fragment and Beyond
Author(s)
Duparc J., Facchini A.
Institution details
Laboratoire Bordelais de Recherche en Informatique et Université de Lausanne
Address
Bordeaux, France
Lausanne, Switzerland
Issued date
2009
Genre
hal-00396433, version 1
Language
english
Abstract
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.
Keywords
µ-calculus, Wadge games, topological complexity, parity games, alternating tree automata, descriptive set theory
Create date
07/01/2010 17:56
Last modification date
20/08/2019 15:59
Usage data