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.