You are not logged in | Log in

Weak index versus Borel rank

Speaker(s)
Filip Murlak
Affiliation
Uniwersytet Warszawski
Date
Feb. 27, 2008, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

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.