Smaller Progress Measures and Separating Automata for Parity Games

Daniele Dell'Erba, Sven Schewe

Calude et al. have recently shown that parity games can be solved in quasi-polynomial time, a landmark result that has led to a number of approaches with quasi-polynomial complexit…