Bisimulation minimisations for Boolean equation systems

Onderzoeksoutput: Boek/rapportRapportAcademic

76 Downloads (Pure)

Samenvatting

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 oblivious 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 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.
Originele taal-2Engels
Plaats van productieEindhoven
UitgeverijTechnische Universiteit Eindhoven
Aantal pagina's22
StatusGepubliceerd - 2009

Publicatie series

NaamComputer science reports
Volume0917
ISSN van geprinte versie0926-4515

Vingerafdruk Duik in de onderzoeksthema's van 'Bisimulation minimisations for Boolean equation systems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Keiren, J., & Willemse, T. A. C. (2009). Bisimulation minimisations for Boolean equation systems. (Computer science reports; Vol. 0917). Technische Universiteit Eindhoven.