Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
From MaRDI portal
Publication:5092368
DOI10.4230/LIPIcs.MFCS.2019.10OpenAlexW2970979881MaRDI QIDQ5092368
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1904.12446
Related Items (10)
The Theory of Universal Graphs for Infinite Duration Games ⋮ Runtime enforcement of hyperproperties ⋮ 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 ⋮ Quasipolynomial computation of nested fixpoints ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
- Solving parity games in big steps
- A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
- The complexity of stochastic games
- Borel determinacy
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Infinite games played on finite graphs
- Fast and simple nested fixpoints
- The complexity of mean payoff games on graphs
- An improved algorithm for the evaluation of fixpoint expressions
- A brief excursion to parity games
- Solving parity games via priority promotion
- Efficient parallel strategy improvement for parity games
- Recursive algorithm for parity games requires exponential time
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Exponential Lower Bounds for Policy Iteration
- Deciding parity games in quasipolynomial time
- A modal μ perspective on solving parity games in quasi-polynomial time
- Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- On model checking for the \(\mu\)-calculus and its fragments
This page was built for publication: Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
