| Issue |
RAIRO-Theor. Inf. Appl.
Volume 33, Number 4-5, July October 1999
|
|
|---|---|---|
| Page(s) | 329 - 339 | |
| DOI | https://doi.org/10.1051/ita:1999121 | |
| Published online | 15 August 2002 | |
The μ-calculus alternation-depth hierarchy is strict on binary trees
LaBRI, Université de Bordeaux 1,
CNRS, 351 cours de la Libération, 33405 Talence, France.
Received:
5
November
1998
Revised:
1
May
1999
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.
Résumé
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.
Mathematics Subject Classification: 68Q68 / 03D05
Key words: Mu-calcul / alternating automata / parity games.
© EDP Sciences, 1999
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.