Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: wadge reducibility

Sortuj według:

Ogranicz wyniki do:

Continuous Separation of Game Languages

Arnold A., Niwiński D.

Fundamenta Informaticae

2007

Vol. 81, nr 1-3

19-28

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.