Theμ-calculus alternation-depth hierarchy is strict on binary trees
André Arnold · RAIRO - Theoretical Informatics and Applications · 1999
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.