Justifications and a Reconstruction of Parity Game Solving Algorithms
arXiv:2102.01440
Abstract
Parity games are infinite two-player games played on directed graphs. Parity game solvers are used in the domain of formal verification. This paper defines parametrized parity games and introduces an operation, Justify, that determines a winning strategy for a single node. By carefully ordering Justify steps, we reconstruct three algorithms well known from the literature.
16 pages, to appear in "LNCS Honorary Volume for Manuel Hermenegildo" [AVERTIS 2019]