Abstract. This paper presents a reduction from the problem of solving parity games to the satisfiability problem for formulas of propositional logic in conjunctive normal form. It uses Jurdziński's characterisation of winning strategies via progress measures. The reduction is motivated by the apparent success that using SAT solvers has had in symbolic verification. The paper reports on a prototype implementation of the reduction and presents some runtime results.
Finally, a different route for tackling µ-calculus model checking is the reduction from parity games to the satisfiability problem, as presented by Lange REF .
Solving parity games by a reduction to SAT
In Proc. of the Workshop on Games in Design and Verification, GDV’05
Mathematics Computer Science