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

Détails

ID Serval
serval:BIB_977532F15AA6
Type
Rapport: document publié par une institution, habituellement élément d'une série.
Sous-type
Working paper: document de travail dans lequel l'auteur présente les résultats de ses travaux de recherche. Les working papers ont pour but de stimuler les discussions scientifiques avec les milieux intéressés et servent de base pour la publication d'articles dans des revues spécialisées.
Collection
Publications
Institution
Titre
The Topological Complexity of Models of the Modal μ-Calculus: On The Alternation Free Fragment and Beyond
Auteur⸱e⸱s
Duparc J., Facchini A.
Détails de l'institution
Laboratoire Bordelais de Recherche en Informatique et Université de Lausanne
Adresse
Bordeaux, France
Lausanne, Switzerland
Date de publication
2009
Genre
hal-00396433, version 1
Langue
anglais
Résumé
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.
Mots-clé
µ-calculus, Wadge games, topological complexity, parity games, alternating tree automata, descriptive set theory
Création de la notice
07/01/2010 16:56
Dernière modification de la notice
20/08/2019 14:59
Données d'usage