Affiliations: LaBRI, University of Bordeaux I, France. E-mail:
[email protected] | Institute of Informatics, Warsaw University, Banacha
2, 02-097 Warszawa, Poland. E-mail: [email protected]
Abstract: 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.
Keywords: Wadge reducibility, infinite trees, automata, Rabin-Mostowski index
