Journal of Applied Mathematics · 2014 · 70 citations · 11 references
ComputingComputer ScienceAlgorithmsFormal MethodsTheory Of ComputationModel CheckingVerificationBounded Model CheckingSymbolic Model Checking
The cost of LTL model checking is highly sensitive to the length of the formula under verification. We observe that, under some specific conditions, the input LTL formula can be reduced to an easier-to-handle one before model checking. In such reduction, these two formulae need not to be logically equivalent, but they share the same counterexample set w.r.t the model. In the case that the model is symbolically represented, the condition enabling such reduction can be detected with a lightweight effort (e.g., with SAT-solving). In this paper, we tentatively name such technique “counterexample-preserving reduction” (C e PR e , for short), and the proposed technique is evaluated by conducting comparative experiments of BDD-based model checking, bounded model checking, and property directed reachability-(IC3) based model checking.
11
The temporal logic of programs
Amir Pnueli · 1977 · 5.7K citations
Symbolic model checking: 1020 States and beyond
Jerry R. Burch, E. M. Clarke, Kenneth L. McMillan et al. · Information and Computation · 1992 · 2.7K citations
On the temporal analysis of fairness
Dov M. Gabbay, Amir Pnueli, Saharon Shelah et al. · 1980 · 731 citations
SAT-based model checking without unrolling
Aaron R. Bradley · 2013 · 491 citations