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-Mostowski index hierarchy of alternating tree automata, forms a hierarchy w.r.t. the Wadge 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.
rabin-mostowski index automata wadge reducibility infinite trees