Sharp Congruences Adequate with Temporal Logics Combining Weak and Strong Modalities

Frédéric Lang, Radu Mateescu, and Franco Mazzanti

Proceedings of the 26th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS'2020), Dublin, Ireland, April 2020

Abstract:

We showed in a recent paper that, when verifying a modal μ-calculus formula, the actions of the system under verification can be partitioned into sets of so-called weak and strong actions, depending on the combination of weak and strong modalities occurring in the formula. In a compositional verification setting, where the system consists of processes executing in parallel, this partition allows us to decide whether each individual process can be minimized for either divergence-preserving branching (if the process contains only weak actions) or strong (otherwise) bisimilarity, while preserving the truth value of the formula. In this paper, we refine this idea by devising a family of bisimilarity relations, named sharp bisimilarities, parameterized by the set of strong actions. We show that these relations have all the nice properties necessary to be used for compositional verification, in particular congruence and adequacy with the logic. We also illustrate their practical utility on several examples and case-studies, and report about our success in the RERS 2019 model checking challenge.

20 pages

PDF

PostScript