Weak automata and Wadge hierarchy

Speaker(s)

Filip Murlak

Affiliation

Uniwersytet Warszawski

Date

Nov. 15, 2006, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

I will show a new lower bound for the height of the Wadge hierarchy of weak tree languages, i. e., the languages of infinite trees recognizable with weak automata. To this end I will prove that the family of weak tree languages is closed by three natural set-theoretic operations that can be used to climb up the hierarchy starting from the simplest sets.

---