Bisimulation minimisations for Boolean equation systems

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

6 Citations (Scopus)

Abstract

Boolean equation systems (BESs) have been used to encode several complex verification problems, including model checking and equivalence checking. We introduce the concepts of strong bisimulation and idempotence-identifying bisimulation for BESs, and we prove that these can be used for minimising BESs prior to solving these. Our results show that large reductions of the BESs may be obtained efficiently. Minimisation is rewarding for BESs with non-trivial alternations: the time required for solving the original BES mostly exceeds the time required for quotienting plus the time for solving the quotient. Furthermore, we provide a verification example that demonstrates that bisimulation minimisation of a process prior to encoding the verification problem on that process as a BES can be arbitrarily less effective than minimising the BES that encodes the verification problem.
Original languageEnglish
Title of host publicationHardware and Software: Verification and Testing (5th International Haifa Verification Conference, HVC 2009, Haifa, Israel, October 19-22, 2009. Revised selected papers)
EditorsK. Namjoshi, A. Zeller, A. Ziv
Place of PublicationBerlin
PublisherSpringer
Pages102-116
ISBN (Print)978-3-642-19236-4
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6405
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Bisimulation minimisations for Boolean equation systems'. Together they form a unique fingerprint.

  • Cite this

    Keiren, J. J. A., & Willemse, T. A. C. (2011). Bisimulation minimisations for Boolean equation systems. In K. Namjoshi, A. Zeller, & A. Ziv (Eds.), Hardware and Software: Verification and Testing (5th International Haifa Verification Conference, HVC 2009, Haifa, Israel, October 19-22, 2009. Revised selected papers) (pp. 102-116). (Lecture Notes in Computer Science; Vol. 6405). Berlin: Springer. https://doi.org/10.1007/978-3-642-19237-1_12