The μ-calculus alternation-depth hierarchy is strict on binary trees
Arnold, André
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 329-339 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_1999__33_4-5_329_0,
     author = {Arnold, Andr\'e},
     title = {The $\mu $-calculus alternation-depth hierarchy is strict on binary trees},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {329-339},
     mrnumber = {1748659},
     zbl = {0945.68118},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_4-5_329_0}
}

Arnold, André. The $\mu $-calculus alternation-depth hierarchy is strict on binary trees. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 329-339. http://gdmltest.u-ga.fr/item/ITA_1999__33_4-5_329_0/

[1] A. Arnold, Logical definability of fixed points. Theoret. Comput Sci. 61 (1988) 289-297. | MR 980247 | Zbl 0663.03024

[2] A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties. Fund. Inform. 4 (1980) 445-476. | MR 604273 | Zbl 0453.68021

[3] A. Arnold and D. Niwiński, Fixed-point characterization of büchi automata on infinite trees. J. Inf. Process. Cybern. EIK 26 (1990). | Zbl 0721.68040

[4] A. Arnold and D. Niwiński, 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. | MR 1196736 | Zbl 0794.03054

[5] J. C. Bradfield, Fixpoint alternation: Arithmetic, transition Systems, and the binary tree, this issue. | Numdam | Zbl 0945.68126

[6] 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. | MR 1480432

[7] 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. | MR 1650761 | Zbl 0892.03005

[8] E. A. Emerson and C. S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS '91. IEEE Computer Society Press (1991) 368-377.

[9] Y. Gurevitch and L. Harrington, Trees, automata and games, in Proc. 14th ACM Symp. on the Theory of Computing (1982) 60-65.

[10] 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. | MR 1464442 | Zbl 1045.03516

[11] A. W. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. | MR 1118576 | Zbl 0728.68086

[12] 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. | MR 1163817 | Zbl 0776.03017

[13] D. E. Muller and P. E. Schupp, Alternating automata on infinite trees, Theoret. Comput. Sci. 54 (1987) 267-276. | MR 919595 | Zbl 0636.68108

[14] D. Niwiński, On fixed point clones, L. Kott, Ed., in Proc. 13th ICALP, Lecture Notes in Comput. Sci. 226 (1986) 464-473. | MR 864709 | Zbl 0596.68036

[15] D. Niwński, Fixed points characterization of infinite behaviour of finite state Systems. Theoret. Comput. Sci. 189 (1997) 1-69. | Zbl 0893.68102

[16] 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. | Zbl 0502.03022

[17] 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. | MR 1462113