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

André Arnold

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1999)

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

How to cite

top

Arnold, André. "The $\mu $-calculus alternation-depth hierarchy is strict on binary trees." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 33.4-5 (1999): 329-339. <http://eudml.org/doc/92607>.

@article{Arnold1999,
author = {Arnold, André},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {alternation-depth hierarchy of the -calculus},
language = {eng},
number = {4-5},
pages = {329-339},
publisher = {EDP-Sciences},
title = {The $\mu $-calculus alternation-depth hierarchy is strict on binary trees},
url = {http://eudml.org/doc/92607},
volume = {33},
year = {1999},
}

TY - JOUR
AU - Arnold, André
TI - The $\mu $-calculus alternation-depth hierarchy is strict on binary trees
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 4-5
SP - 329
EP - 339
LA - eng
KW - alternation-depth hierarchy of the -calculus
UR - http://eudml.org/doc/92607
ER -

References

top
  1. [1] A. Arnold, Logical definability of fixed points. Theoret. Comput Sci. 61 (1988) 289-297. Zbl0663.03024MR980247
  2. [2] A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties. Fund. Inform. 4 (1980) 445-476. Zbl0453.68021MR604273
  3. [3] A. Arnold and D. Niwiński, Fixed-point characterization of büchi automata on infinite trees. J. Inf. Process. Cybern. EIK 26 (1990). Zbl0721.68040
  4. [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. Zbl0794.03054MR1196736
  5. [5] J. C. Bradfield, Fixpoint alternation: Arithmetic, transition Systems, and the binary tree, this issue. Zbl0945.68126
  6. [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. MR1480432
  7. [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.03005MR1650761
  8. [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. [9] Y. Gurevitch and L. Harrington, Trees, automata and games, in Proc. 14th ACM Symp. on the Theory of Computing (1982) 60-65. 
  10. [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. Zbl1045.03516MR1464442
  11. [11] A. W. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. Zbl0728.68086MR1118576
  12. [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. Zbl0776.03017MR1163817
  13. [13] D. E. Muller and P. E. Schupp, Alternating automata on infinite trees, Theoret. Comput. Sci. 54 (1987) 267-276. Zbl0636.68108MR919595
  14. [14] D. Niwiński, On fixed point clones, L. Kott, Ed., in Proc. 13th ICALP, Lecture Notes in Comput. Sci. 226 (1986) 464-473. Zbl0596.68036MR864709
  15. [15] D. Niwński, Fixed points characterization of infinite behaviour of finite state Systems. Theoret. Comput. Sci. 189 (1997) 1-69. Zbl0893.68102
  16. [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
  17. [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. MR1462113

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.