Star Height via Games
Mikołaj Bojańczyk · 2015
This paper proposes a new algorithm deciding the star height problem. As shown by Kirsten, the star height problem reduces to a problem concerning automata with counters, called limitedness. The new contribution is a different algorithm for the limitedness problem, which reduces it to solving a Gale-Stewart game with an ω-regular winning condition.