Check It Out: On the Efficient Formal Verification of Live Sequence Charts

Klose, Jochen and Toben, Tobe and Westphal, Bernd and Wittke, Hartmut
Live Sequence Charts (LSCs) are an established visual formalism for requirements in formal, model-based development, in particular aiming at formal verification of the model. The model-checking problem for LSCs is principally long solved as each LSC has an equivalent LTL formula, but even for moderate sized LSCs the formulae grow prohibitively large. In this paper we elaborate on practically relevant subclasses of LSCs, namely bonded and time bounded, which don?t require the full power of LTL model-checking. For bonded LSCs, a combination of observer automaton and fixed small liveness property and for additionally time bounded LSCs reachability checking is sufficient.
08 / 2006