You are not logged in | Log in

Star height via games

Speaker(s)
Mikołaj Bojańczyk
Affiliation
Uniwersytet Warszawski
Date
April 23, 2014, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

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.