zbMATH — the first resource for mathematics

The \(\mu\)-calculus alternation-depth hierarchy is strict on binary trees. (English) Zbl 0945.68118
Summary: We give a simple proof that the alternation-depth hierarchy of the \(\mu\)-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.

68Q45 Formal languages and automata
03D05 Automata and formal grammars in connection with logical questions
Full Text: DOI EuDML
[1] A. Arnold, Logical definability of fixed points. Theoret. Comput. Sci.61 (1988) 289-297. · Zbl 0663.03024 · doi:10.1016/0304-3975(88)90129-6
[2] A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties. Fund. Inform.4 (1980) 445-476. Zbl0453.68021 · Zbl 0453.68021
[3] A. Arnold and D. Niwinski, Fixed-point characterization of büchi automata on infinite trees. J. Inf. Process. Cybern. EIK26 (1990). · Zbl 0721.68040
[4] 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. · Zbl 0794.03054
[5] J.C. Bradfield, Fixpoint alternation: Arithmetic, transition systems, and the binary tree, this issue. · Zbl 0945.68126 · doi:10.1051/ita:1999122 · eudml:221964
[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.
[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. Zbl0892.03005 · 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. · Zbl 1045.03516
[11] A.W. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci.83 (1991) 323-335. · Zbl 0728.68086 · doi:10.1016/0304-3975(91)90283-8
[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. · Zbl 0776.03017 · doi:10.1016/0304-3975(92)90076-R
[13] D.E. Muller and P.E. Schupp, Alternating automata on infinite trees, Theoret. Comput. Sci.54 (1987) 267-276. Zbl0636.68108 · Zbl 0636.68108 · doi:10.1016/0304-3975(87)90133-2
[14] D. Niwinski, On fixed point clones, L. Kott, Ed., in Proc. 13th ICALP, Lecture Notes in Comput. Sci.226 (1986) 464-473.
[15] D. Niwinski, Fixed points characterization of infinite behaviour of finite state systems. Theoret. Comput. Sci.189 (1997) 1-69. · Zbl 0893.68102 · doi:10.1016/S0304-3975(97)00039-X
[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. Zbl0502.03022 · 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. · Zbl 1434.03105
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.