Continuous Separation of Game Languages

We show that a family of tree languages W _{(l,k)} , previously used by J. Bradfield, and by the first author to show the strictness of the Rabin¨CMostowski index hierarchy of alternating tree automata, forms a hierarchy w.r.t. theWadge reducibility. That is, W _{(l,k) ⩽ _W W _{(l',k')} if and only if the index (l', k') is above (l, k). This is one of the few separation results known so far, concerning the topological complexity of non-deterministically recognizable tree languages, and one of the few results about finite-state recognizable non-Borel sets of trees.