Nie jesteś zalogowany | Zaloguj się

Weak index versus Borel rank

Prelegent(ci)
Filip Murlak
Afiliacja
Uniwersytet Warszawski
Termin
27 lutego 2008 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

I will talk about weak recognizability of deterministic languages of infinite trees. I will prove that for deterministic languages the Borel hierarchy and the weak index hierarchy coincide. Furthermore, I will propose a procedure computing for a deterministic automaton an equivalent minimal index weak automaton with a quadratic number of states.