December 21, 2017Presentation: State of the art parity game solving
Room: Hal B 2ATom van Dijk

Parity games are deceptively simple two-player games on directed graphs
labeled with numbers.

Parity games have important practical applications in formal
verification and synthesis, especially to solve the model-checking problem
of the modal mu-calculus. They are also interesting from the theory
perspective, because they are widely believed to admit a polynomial
solution, but so far no such algorithm is known. In recent years, a number
of new algorithms and improvements to existing algorithms have been
In this talk, we introduce parity games in an accessible way and discuss
why they are so interesting. We present various solutions that have been
proposed over the years. We also present a comprehensive empirical evaluation
of modern parity game algorithms and solvers, both on real world benchmarks
and randomly generated games.