Games for the Wadge Hierarchy of Deterministic Tree Languages

Prelegent(ci)

Filip Murlak

Afiliacja

Uniwersytet Warszawski

Termin

18 stycznia 2006 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

In the case of infinite words, the hierarchy of regular languages defined by continuous reductions is well understood since Wagner's 1977 paper. In particular, there exists a procedure calculating the exact level of a given language in the Wadge hierarchy. We will consider an analogous problem for tree languages. In the case of languages of infinite words, there exists a continuous reduction from L to M , iff Duplicator has a winning strategy in the Wadge game G(L,M) . For recognizable languages, an equivalent criterion is the existance of a finite-state transducer reducing L to M . The last property is no more true for trees. However, we manage to adapt the Wadge games to the case of deterministically recognizable tree languages in such a way that the crucial property is maintained. We reinterpret this game entirely in terms of automata recognisnig the languages and using this tool we provide an effective description of the Wadge hierarchy of deterministic tree languages.

---