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
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.