Campus Event Calendar
Event Entry
What and Who
The Wadge Hierarchy of Deterministic Tree Languages
Filip Murlak
Warsaw University
Talk
AG 1, AG 2, AG 3, AG 4, AG 5
Expert Audience
-- Not specified --
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 11 April 2006
10:30
-- Not specified --
E1 3 - Hörsaal Gebäude
528
Saarbrücken
Abstract
The hierarchy induced by the existence of continuous reductions between
regular languages of infinite words 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 regular
languages of infinite words, 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.
regular languages of infinite words 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 regular
languages of infinite words, 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.
Contact
Bernd Finkbeiner
--email hidden
passcode not visible
logged in users only
Veronika Weinand, 04/10/2006 15:20 -- Created document.