Nie jesteś zalogowany | Zaloguj się

Star height via games

Prelegent(ci)
Mikołaj Bojańczyk
Afiliacja
Uniwersytet Warszawski
Termin
23 kwietnia 2014 14:15
Pokój
p. 5870
Seminarium
Seminarium „Teoria automatów”

I will show a simplified proof of decidability for the star height problem. The simplified proof follows the same lines as the proof of Daniel Kirsten: first the star height problem is reduced to the limitedness problem for certain counter automata, and then the limitedness problem is solved. The simplification concerns the limitedness problem, while the reduction to limitedness is the same as in previous proofs. The new idea is to phrase the limitedness problem as a game, and use finite memory determinacy for games with omega-regular winning conditions.