This is joint work with Filip Murlak (Warsaw).

We consider languages of infinite binary trees which are recognized by both Büchi and co-Büchi automata, or equivalently which satisfy a $\mu$-calculus formula with no alternation of greatest or lowest fixpoints.

We use game theoretical methods from Descriptive Set Theory to classify such languages with respect to their topological complexity.

More precisely, these languages are sets of infinite binary trees recognized by alternating automata. Alternation is a notion of

acceptance which not only extends non determinism, but is based on the existence of a winning strategy for a player in

an infinite game. In fact, we consider alternating tree automata with weak parity acceptance conditions.

So these automata are very strong because of the alternation, but also weak in terms of acceptance condition.

This weakness means that every state is associated to some integer called its priority. Given any state $q$, the priority of all accessible states from

$q$ is at least the one of $q$. The acceptation or rejection of infinite binary trees relies then on the existence of a

winning strategy for one of the two players in a parity game, that is a game consisting in pushing a token along a

branch of the computation tree. The player to whom the current node belongs to, choosing a successor node to push

the token further onto. We show that the language recognized by such an automaton with priorities in $[0,n]$ is $\Pi^0_n$, and in

$[1,n+1]$ is $\Sigma^0_n$. We show that the Wadge Hierarchy of these languages not only contains complete sets for all

finite differences of $\Pi^0_n$ and $\Sigma^0_n$ sets, but much more since the whole hierarchy has length at least

$\epsilon_0$, the first fixpoint of the arithmetical operation $x\longmapsto \omega^x$. Hence, much higher that the Wadge

hierarchy of deterministic tree languages unearthed by Filip Murlak in a recent paper which received the ICALP best paper award.