A workbench for preprocessor design and evaluation: toward benchmarks for parity games

Abstract

We describe a prototype workbench for the study of parity games and their solvers. This workbench is aimed at facilitating two activities: to aid in the design, validation, and evaluation of preprocessors for parity game solvers; and to aid in the generation of benchmark parity games that are meaningful for a wide range of solvers. Our workbench allows for easy composition of preprocessors, can populate databases with games and their meta-data, offers a query language for generating games of interest, and has already found potentially hard games.