We show that a family of tree languages W(i,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, [formula] if and only if the index [...] is above (i,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.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.