Analysis of Boolean equation systems through structure graphs

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

2 Citations (Scopus)

Abstract

We analyse the problem of solving Boolean equation systems through the use of structure graphs. The latter are obtained through an elegant set of Plotkin-style deduction rules. Our main contribution is that we show that equation systems with bisimilar structure graphs have the same solution. We show that our work conservatively extends earlier work, conducted by Keiren and Willemse, in which dependency graphs were used to analyse a subclass of Boolean equation systems, viz., equation systems in standard recursive form. We illustrate our approach by a small example, demonstrating the effect of simplifying an equation system through minimisation of its structure graph.
Original languageEnglish
Title of host publicationProceedings 6th Workshop on Structural Operational Semantics (SOS 2009, Bologna, Italy, August 31, 2009)
EditorsB. Klin, P. Sobocinski
Pages92-107
DOIs
Publication statusPublished - 2010

Publication series

NameElectronic Proceedings in Theoretical Computer Science
Volume18
ISSN (Print)2075-2180

Cite this