Invited Talk: Igor Walukiewicz

Alternation hierarchies

In analogy with classical quantifier alternation hierarchies one can define the hierarchies based on alternation of least and greatest fixpoints. If we take a decidable logic as the propositional mu-calculus is decidable so we can hope to understand its fixpoint alternation hierarchy from the algorithmic point of view. Since a decade we know that the fixpoint hierarchy is infinite. We have also examples of hard languages for each level of the hierarchy. Still, we are quite far from settling the decidability question: given a regular tree language compute its level in the hierarchy. In this talk will survey the present status some results on this problem. Using the connection between the mu-calculus and automata, the talk will rather look at different hierarchies in the automata setting. Topological hierarchy based on Wadge reducibility will be also discussed.