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.

---