Partial-Order Reduction for Parity Games with an Application on Parameterised Boolean Equation Systems

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Partial-order reduction (POR) is a well-established technique to combat the problem of state-space explosion. We propose POR techniques that are sound for parity games, a well-established formalism for solving a variety of decision problems. As a consequence, we obtain the first POR method that is sound for model checking for the full modal μ-calculus. Our technique is applied to, and implemented for the fixed point logic called parameterised Boolean equation systems, which provides a high-level representation of parity games. Experiments indicate that substantial reductions can be achieved.

Original languageEnglish
Title of host publicationTools and Algorithms for the Construction and Analysis of Systems- 26th International Conference, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Proceedings, Part II
EditorsArmin Biere, David Parker
PublisherSpringer
Pages307-324
Number of pages18
ISBN (Print)9783030452360
DOIs
Publication statusPublished - 17 Apr 2020
Event26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020 - Dublin, Ireland
Duration: 25 Apr 202030 Apr 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12079 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020
CountryIreland
CityDublin
Period25/04/2030/04/20

Fingerprint Dive into the research topics of 'Partial-Order Reduction for Parity Games with an Application on Parameterised Boolean Equation Systems'. Together they form a unique fingerprint.

  • Cite this

    Neele, T., Willemse, T. A. C., & Wesselink, W. (2020). Partial-Order Reduction for Parity Games with an Application on Parameterised Boolean Equation Systems. In A. Biere, & D. Parker (Eds.), Tools and Algorithms for the Construction and Analysis of Systems- 26th International Conference, TACAS 2020, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020, Proceedings, Part II (pp. 307-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12079 LNCS). Springer. https://doi.org/10.1007/978-3-030-45237-7_19