You are not logged in | Log in

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.