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

André Arnold

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Arnold, 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
  1. A. Arnold, Logical definability of fixed points. Theoret. Comput. Sci.61 (1988) 289-297.  
  2. A. Arnold and M. Nivat, The metric space of infinite trees. Algebraic and topological properties. Fund. Inform.4 (1980) 445-476.  
  3. A. Arnold and D. Niwinski, Fixed-point characterization of büchi automata on infinite trees. J. Inf. Process. Cybern. EIK26 (1990).  
  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.  
  5. J.C. Bradfield, Fixpoint alternation: Arithmetic, transition systems, and the binary tree, this issue.  
  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.  
  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.  
  11. A.W. Mostowski, Hierarchies of weak automata and weak monadic formulas. Theoret. Comput. Sci.83 (1991) 323-335.  
  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.  
  13. D.E. Muller and P.E. Schupp, Alternating automata on infinite trees, Theoret. Comput. Sci.54 (1987) 267-276.  
  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.  
  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.  
  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.  

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.