Improving the Encoding of LTL Model Checking into SAT

Bounded Model Checking (BMC) is a technique for encoding an LTL model checking problem into a problem of propositional satisfiability. Since the seminal paper by Biere et al. [2], the research on BMC has been primarily directed at achieving higher efficiency for solving reachability properties. In this paper, we tackle the problem of improving BMC encodings for the full class of LTL properties. We start noticing some properties of the encoding of [2], and we exploit them to define improvements that make the resulting boolean formulas smaller or simpler to solve. © Springer-Verlag Berlin Heidelberg 2002.