Size matters in the modal $\mu$-calculus

Clemens Kupke, Johannes Marti, Yde Venema

We discuss and compare complexity measures for the modal $\mu$-calculus, focusing on size and alternation depth. As a yardstick we take Wilke's alternating tree automata, which we sh…