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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.

Originele taal-2Engels
TitelTools 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
RedacteurenArmin Biere, David Parker
UitgeverijSpringer
Pagina's307-324
Aantal pagina's18
ISBN van geprinte versie9783030452360
DOI's
StatusGepubliceerd - 17 apr 2020
Evenement26th 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, Ierland
Duur: 25 apr 202030 apr 2020

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12079 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres26th 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
LandIerland
StadDublin
Periode25/04/2030/04/20

Vingerafdruk Duik in de onderzoeksthema's van 'Partial-Order Reduction for Parity Games with an Application on Parameterised Boolean Equation Systems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    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 (editors), 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 (blz. 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