# The μ-calculus alternation-depth hierarchy is strict on binary trees

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 4-5, page 329-339
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topArnold, André. "The μ-calculus alternation-depth hierarchy is strict on binary trees." RAIRO - Theoretical Informatics and Applications 33.4-5 (2010): 329-339. <http://eudml.org/doc/222087>.

@article{Arnold2010,

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.
},

author = {Arnold, André},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Mu-calcul; alternating automata; parity games.; alternation-depth hierarchy of the -calculus},

language = {eng},

month = {3},

number = {4-5},

pages = {329-339},

publisher = {EDP Sciences},

title = {The μ-calculus alternation-depth hierarchy is strict on binary trees},

url = {http://eudml.org/doc/222087},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Arnold, André

TI - The μ-calculus alternation-depth hierarchy is strict on binary trees

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 4-5

SP - 329

EP - 339

AB - 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.

LA - eng

KW - Mu-calcul; alternating automata; parity games.; alternation-depth hierarchy of the -calculus

UR - http://eudml.org/doc/222087

ER -

## References

top- A. Arnold, Logical definability of fixed points. Theoret. Comput. Sci.61 (1988) 289-297.
- A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties. Fund. Inform.4 (1980) 445-476.
- A. Arnold and D. Niwinski, Fixed-point characterization of büchi automata on infinite trees. J. Inf. Process. Cybern. EIK26 (1990).
- A. Arnold and D. Niwinski, Fixed point characterization of weak monadic logic definable sets of trees, M. Nivat and A. Podelski, Eds., Tree automata and Languages. Elsevier (1992) 159-188.
- J.C. Bradfield, Fixpoint alternation: Arithmetic, transition systems, and the binary tree, this issue.
- J.C. Bradfield, The modal mu-calculus alternation hierarchy is strict, U. Montanari and V. Sassone, Eds., in Proc. CONCUR '96, Lecture Notes in Comput. Sci.1119 (1996) 233-246.
- J.C. Bradfield, Simplifying the modal mu-calculus alternation hierarchy, M. Morvan, C. Meinel and D. Krob, Eds., in Proc. STACS '98, Lecture Notes in Comput. Sci.1373 (1998) 39-49.
- E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS '91. IEEE Computer Society Press (1991) 368-377.
- Y. Gurevitch and L. Harrington, Trees, automata and games, in Proc. 14th ACM Symp. on the Theory of Computing (1982) 60-65.
- G. Lenzi, A hierarchy theorem for the mu-calculus, F. Meyer auf der Heide and B. Monien, Eds., in Proc. ICALP '96, Lecture Notes in Comput. Sci.1099 (1996) 87-109.
- A.W. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci.83 (1991) 323-335.
- D.E. Muller, A. Saoudi and P.E. Schupp, Alternating automata, the weak monadic theory of the tree and its complexity. Theoret. Comput. Sci.97 (1992) 233-244.
- D.E. Muller and P.E. Schupp, Alternating automata on infinite trees, Theoret. Comput. Sci.54 (1987) 267-276.
- D. Niwinski, On fixed point clones, L. Kott, Ed., in Proc. 13th ICALP, Lecture Notes in Comput. Sci.226 (1986) 464-473.
- D. Niwinski, Fixed points characterization of infinite behaviour of finite state systems. Theoret. Comput. Sci.189 (1997) 1-69.
- W. Thomas, A hierarchy of sets of infinite trees, A.B. Cremers and H.P. Kriegel, Eds., Theoret. Comput. Sci., Lecture Notes in Comput. Sci.145 (1983) 335-342.
- I. Walukiewicz, Monadic second-order logic on tree-like structures, C. Puech and R. Reischuk, Eds., in Proc. STACS '96, Lecture Notes in Comput. Sci.1046 (1996) 401-414.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.