Partial Order Reduction for State/Event LTL with Application to Component-Interaction Automata

Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BENEŠ Nikola BRIM Luboš BÜHNOVÁ Barbora ČERNÁ Ivana SOCHOR Jiří MORAVCOVÁ VAŘEKOVÁ Pavlína

Year of publication 2011
Type Article in Periodical
Magazine / Source Science of Computer Programming
MU Faculty or unit

Faculty of Informatics

Citation
Web http://dx.doi.org/10.1016/j.scico.2010.02.008
Doi http://dx.doi.org/10.1016/j.scico.2010.02.008
Field Informatics
Keywords State/event LTL; Partial order reduction; Formal verification; Model checking; Component-based systems; Component-interaction automata
Attached files
Description Software systems assembled from autonomous components become an interesting target for formal verification due to the issue of correct interplay in component interaction. State/event LTL (Chaki et al. 2004, 2005) incorporates both states and events to express important properties of component-based software systems. The main contribution of this paper is a partial order reduction technique for verification of state/event LTL properties. The core is a novel notion of stuttering equivalence. The positive attribute of the equivalence is that it can be resolved with existing methods for partial order reduction. State/event LTL properties are, in general, not preserved under state/event stuttering equivalence. To this end we define a new logic, called weak state/event LTL, which is invariant under the new equivalence. To bring some evidence of the method’s efficiency, we present the results obtained by employing the partial order reduction technique within our tool for verification of component-based systems.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.