×

Completeness and complexity of bounded model checking. (English) Zbl 1202.68244

Steffen, Bernhard (ed.) et al., Verification, model checking, and abstract interpretation. 5th international conference, VMCAI 2004, Venice, Italy, January 11–13, 2004. Proceedings. Berlin: Springer (ISBN 3-540-20803-8/pbk). Lect. Notes Comput. Sci. 2937, 85-96 (2004).
Summary: For every finite model \(M\) and an LTL property \(\varphi \), there exists a number \( \mathcal{CT}\) (the Completeness Threshold) such that if there is no counterexample to \(\varphi \) in \(M\) of length \( \mathcal{CT}\) or less, then \(M \models \varphi \). Finding this number, if it is sufficiently small, offers a practical method for making Bounded Model Checking complete. We describe how to compute an over-approximation to \( \mathcal{CT}\) for a general LTL property using Büchi automata, following the Vardi-Wolper LTL model checking framework. Based on the value of \( \mathcal{CT}\), we prove that the complexity of standard SAT-based BMC is doubly exponential, and that consequently there is a complexity gap of an exponent between this procedure and standard LTL model checking. We discuss ways to bridge this gap.
The article mainly focuses on observations regarding bounded model checking rather than on a presentation of new techniques.
For the entire collection see [Zbl 1031.68005].

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI