A modal μ perspective on solving parity games in quasi-polynomial time

DOI10.1145/3209108.3209115zbMath1497.68228OpenAlexW2799045007MaRDI QIDQ5145340

Karoliina Lehtinen

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3209108.3209115

zbMATH Keywords

parity gamesalgorithmic complexitydescriptive complexitymodal \(\mu\) calculus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Games involving graphs (91A43) Modal logic (including the logic of norms) (03B45) Descriptive complexity and finite models (68Q19)

Related Items (20)

The Theory of Universal Graphs for Infinite Duration Games ⋮ Deciding Parity Games in Quasi-polynomial Time ⋮ Unnamed Item ⋮ Finite-state strategies in delay games ⋮ Robust worst cases for parity games algorithms ⋮ Reachability games and parity games ⋮ Universal algorithms for parity games and nested fixpoints ⋮ Improved complexity analysis of quasi-polynomial algorithms solving parity games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improving parity games in practice ⋮ Quasipolynomial computation of nested fixpoints ⋮ Synthesizing optimally resilient controllers ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time ⋮ On the Way to Alternating Weak Automata

This page was built for publication: A modal μ perspective on solving parity games in quasi-polynomial time