Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving …