zbMATH — the first resource for mathematics

Efficient decision procedures for model checking of linear time logic properties. (English) Zbl 1046.68579
Halbwachs, Nicolas (ed.) et al., Computer aided verification. 11th international conference, CAV ’99. Trento, Italy, July 6–10, 1999. Proceedings. Berlin: Springer (ISBN 3-540-66202-2). Lect. Notes Comput. Sci. 1633, 222-235 (1999).
Summary: We propose an algorithm for LTL model checking based on the classification of the automata and on guided symbolic search. Like most current methods for LTL model checking, our algorithm starts with a tableau construction and uses a model checker for CTL with fairness constraints to prove the existence of fair paths. However. we classify the tableaux according to their structure, and use efficient decision procedures for each class. Guided search applies hints to constrain the transition relation during fixpoint computations. Each fixpoint is thus translated into a sequence of fixpoints that are often much easier to compute than the original one. Our preliminary experimental results suggest that the new algorithm for LTL is quite efficient. In fact, for properties that can be expressed in both CTL and LTL, the algorithm is competitive with the CTL model checking algorithm.
For the entire collection see [Zbl 0925.68015].

68Q60 Specification and verification (program logics, model checking, etc.)