Justifications and a Reconstruction of Parity Game Solving Algorithms

2021/02/02 by Lapauw, Ruben, Bruynooghe, Maurice, Denecker, Marc
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/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.

Related

• Graph Operations on Parity Games and Polynomial-Time Algorithms
• On-The-Fly Solving for Symbolic Parity Games
• Parity Game Reductions
• An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space
• Partial Solvers for Generalized Parity Games