Theμ-calculus alternation-depth hierarchy is strict on binary trees
- 1 July 1999
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 33 (4-5) , 329-339
- https://doi.org/10.1051/ita:1999121
Abstract
In this paper we give a simple proof that the alternation-depth hierarchy of the μ-calculus for binary trees is strict. The witnesses for this strictness are the automata that determine whether there is a winning strategy for the parity game played on a tree. Nous donnons dans cet article une preuve simple que la hiérarchie d'alter nance de points fixes pour le μ-calcul sur les arbres binaires est infinie. Les témoins en sont les automates qui déterminent l'existence d'une stratégie gagnante pour le jeu de parité joué sur un arbre binaire.Keywords
This publication has 12 references indexed in Scilit:
- A hierarchy of sets of infinite treesPublished by Springer Nature ,2006
- Simplifying the modal mu-calculus alternation hierarchyPublished by Springer Nature ,1998
- Fixed point characterization of infinite behavior of finite-state systemsTheoretical Computer Science, 1997
- The modal mu-calculus alternation hierarchy is strictPublished by Springer Nature ,1996
- A hierarchy theorem for the μ-calculusPublished by Springer Nature ,1996
- Alternating automata, the weak monadic theory of trees and its complexityTheoretical Computer Science, 1992
- Hierarchies of weak automata and weak monadic formulasTheoretical Computer Science, 1991
- Logical definability of fixed pointsTheoretical Computer Science, 1988
- Alternating automata on infinite treesTheoretical Computer Science, 1987
- On fixed-point clonesPublished by Springer Nature ,1986