Content Tags

There are no tags.

Oink: an Implementation and Evaluation of Modern Parity Game Solvers.

RSS Source
Authors
Tom van Dijk

Parity games have important practical applications in formal verification andsynthesis, especially to solve the model-checking problem of the modalmu-calculus. They are also interesting from the theory perspective, as they arewidely believed to admit a polynomial solution, but so far no such algorithm isknown. In recent years, a number of new algorithms and improvements to existingalgorithms have been proposed. We implement a new and easy to extend tool Oink,which is a high-performance implementation of modern parity game algorithms. Wefurther present a comprehensive empirical evaluation of modern parity gamealgorithms and solvers, both on real world benchmarks and randomly generatedgames. Our experiments show that our new tool Oink outperforms the currentstate-of-the art.

Stay in the loop.

Subscribe to our newsletter for a weekly update on the latest podcast, news, events, and jobs postings.