zbMATH — the first resource for mathematics

Incremental and complete bounded model checking for full PLTL. (English) Zbl 1081.68621
Etessami, Kousha (ed.) et al., Computer aided verification. 17th international conference, CAV 2005, Edinburgh, Scotland, UK, July 6–10, 2005. Proceedings. Berlin: Springer (ISBN 3-540-27231-3/pbk). Lecture Notes in Computer Science 3576, 98-111 (2005).
Summary: Bounded model checking is an efficient method for finding bugs in system designs. The major drawback of the basic method is that it cannot prove properties, only disprove them. Recently, some progress has been made towards proving properties of LTL. We present an incremental and complete bounded model checking method for the full linear temporal logic with past (PLTL). Compared to previous works, our method both improves and extends current results in many ways: (i) our encoding is incremental, resulting in improvements in performance, (ii) we can prove non-existence of a counterexample at shallower depths in many cases, and (iii) we support full PLTL. We have implemented our method in the NuSMV2 model checker and report encouraging experimental results.
For the entire collection see [Zbl 1078.68004].

68Q60 Specification and verification (program logics, model checking, etc.)
MiniSat; NuSMV; SATIRE; Chaff
PDF BibTeX Cite
Full Text: DOI