A technique to speed up symmetric attractor-based algorithms for parity games
KS Thejaswini, P Ohlmann… - Proceedings of the 42nd …, 2022 - wrap.warwick.ac.uk
The classic McNaughton-Zielonka algorithm for solving parity games has excellent
performance in practice, but its worst-case asymptotic complexity is worse than that of the …
performance in practice, but its worst-case asymptotic complexity is worse than that of the …
Avoiding distractions in parity games
T van Dijk - International Symposium on Leveraging Applications of …, 2024 - Springer
We consider algorithms for parity games that use attractor decomposition, such as Zielonka's
recursive algorithm, priority promotion, and tangle learning. In earlier work, we identified the …
recursive algorithm, priority promotion, and tangle learning. In earlier work, we identified the …
Fatal attractors in parity games: Building blocks for partial solvers
M Huth, JHP Kuo, N Piterman - arXiv preprint arXiv:1405.0386, 2014 - arxiv.org
Attractors in parity games are a technical device for solving" alternating" reachability of given
node sets. A well known solver of parity games-Zielonka's algorithm-uses such attractor …
node sets. A well known solver of parity games-Zielonka's algorithm-uses such attractor …
Winning cores in parity games
S Vester - Proceedings of the 31st Annual ACM/IEEE Symposium …, 2016 - dl.acm.org
We introduce the novel notion of winning cores in parity games and develop a deterministic
polynomial-time under-approximation algorithm for solving parity games based on winning …
polynomial-time under-approximation algorithm for solving parity games based on winning …
Parallel parity games: a multicore attractor for the zielonka recursive algorithm
Parity games are abstract infinite-duration two-player games, widely studied in computer
science. Several solution algorithms have been proposed and also implemented in the …
science. Several solution algorithms have been proposed and also implemented in the …
Fatal attractors in parity games
M Huth, JHP Kuo, N Piterman - … on Foundations of Software Science and …, 2013 - Springer
We study a new form of attractor in parity games and use it to define solvers that run in
PTIME and are partial in that they do not solve all games completely. Technically, for color c …
PTIME and are partial in that they do not solve all games completely. Technically, for color c …
A Matrix-Based Approach to Parity Games
S Aggarwal, AS De La Banda, L Yang… - … Conference on Tools …, 2023 - Springer
Parity games are two-player zero-sum games of infinite duration played on finite graphs for
which no solution in polynomial time is still known. Solving a parity game is an NP∩ co-NP …
which no solution in polynomial time is still known. Solving a parity game is an NP∩ co-NP …
Parity games: Zielonka's algorithm in quasi-polynomial time
P Parys - arXiv preprint arXiv:1904.12446, 2019 - arxiv.org
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
A recursive approach to solving parity games in quasipolynomial time
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest
among the many existing parity game algorithms. However, its complexity is exponential …
among the many existing parity game algorithms. However, its complexity is exponential …
Universal algorithms for parity games and nested fixpoints
An attractor decomposition meta-algorithm for solving parity games is given that generalises
the classic McNaughton-Zielonka algorithm and its recent quasi-polynomial variants due to …
the classic McNaughton-Zielonka algorithm and its recent quasi-polynomial variants due to …