Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games

DOI10.1137/1.9781611975482.142zbMath1432.68223arXiv1807.10546OpenAlexW3099407508MaRDI QIDQ5236329

Nathanaël Fijalkow, Wojciech Czerwiński, Ranko Lazić, Paweł Parys, Marcin Jurdziński, Laure Daviaud

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.10546

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (11)

The Theory of Universal Graphs for Infinite Duration Games ⋮ A survey on satisfiability checking for the \(\mu \)-calculus through tree automata ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quasipolynomial computation of nested fixpoints ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ Unnamed Item

This page was built for publication: Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games