< Back to previous page


Improving Parity Game Solvers with Justifications

Book Contribution - Book Chapter Conference Contribution

Parity games are infinite two-player games played on node-weighted directed graphs. Formal verification problems such as verifying and synthesizing automata, bounded model checking of LTL, CTL*, propositional ยต-calculus, ...reduce to problems over parity games. The core problem of parity game solving is deciding the winner of some (or all) nodes in a parity game. In this paper, we improve several parity game solvers by using a justification graph. Experimental evaluation shows our algorithms improve upon the state-of-the-art.
Book: Proceedings of VMCAI 2020
Pages: 449 - 470
Number of pages: 22
Publication year:2020