Abstract
Parameterised Boolean Equation Systems (PBESs) can be used to represent many different kinds of decision problems. Most notably, model checking and equivalence problems can be encoded in a PBES. Traditional techniques to solve PBESs, such as instantiation techniques, cannot deal with PBESs with an infinite data domain. We propose an approach that can solve PBESs with infinite data by computing the bisimulation quotient of the underlying graph structure. Furthermore, we show how this technique can be improved by repeatedly searching for finite proofs. We also apply knowledge of intermediate solutions in an early termination heuristic. Unlike existing approaches, our technique is not restricted to subfragments of PBESs. Compared to similar procedures that operate on behavioural models, our technique is also more general: it is not restricted to model checking with finite action sets. Experimental results show that our ideas work well in practice and support a wider range of models and properties than state-of-the-art techniques.
Original language | English |
---|---|
Article number | 102389 |
Number of pages | 22 |
Journal | Science of Computer Programming |
Volume | 188 |
DOIs | |
Publication status | Published - 1 Mar 2020 |
Keywords
- Bisimulation
- Infinite state system
- Modal mu-calculus
- Parameterised Boolean equation system
- Symbolic model checking
Fingerprint
Dive into the research topics of 'Finding compact proofs for infinite-data parameterised Boolean equation systems'. Together they form a unique fingerprint.Datasets
-
Infinite-data PBES Quotienting with the mCRL2 toolset
Neele, T. (Contributor), Willemse, T. A. C. (Contributor) & Groote, J. F. (Contributor), Zenodo, 4 Nov 2019
Dataset