The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
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
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.
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 -
- 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
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.