Finding compact proofs for infinite-data parameterised Boolean equation systems

Research output: Contribution to journalArticleAcademicpeer-review

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 languageEnglish
Article number102389
Number of pages22
JournalScience of Computer Programming
Volume188
DOIs
Publication statusPublished - 1 Mar 2020

    Fingerprint

Keywords

  • Bisimulation
  • Infinite state system
  • Modal mu-calculus
  • Parameterised Boolean equation system
  • Symbolic model checking

Cite this