Improved complexity analysis of quasi-polynomial algorithms solving parity games
From MaRDI portal
Publication:6149052
DOI10.1007/978-3-031-36978-0_22arXiv2305.00308OpenAlexW4384788699MaRDI QIDQ6149052
Aleksander Wiącek, Paweł Parys
Publication date: 12 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2305.00308
Cites Work
- Unnamed Item
- 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
- Infinite games on finitely coloured graphs with applications to automata on infinite trees
- Fast and simple nested fixpoints
- An improved algorithm for the evaluation of fixpoint expressions
- Solving parity games via priority promotion
- A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games
- A Deterministic Subexponential Algorithm for Solving Parity Games
- Exponential Lower Bounds for Policy Iteration
- Deciding parity games in quasipolynomial time
- On the Way to Alternating Weak Automata
- Parity Games: Zielonka's Algorithm in Quasi-Polynomial 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: Improved complexity analysis of quasi-polynomial algorithms solving parity games
