A Compact Linear Translation for Bounded Model Checking

We present a syntactic scheme for translating future-time LTL bounded model checking problems into propositional satisfiability problems. The scheme is similar in principle to the Separated Normal Form encoding proposed in [Frisch, A., D. Sheridan and T. Walsh, A fixpoint based encoding for bounded model checking, in: M.D. Aagaard and J.W. O'Leary, editors, Formal Methods in Computer-Aided Design; 4th International Conference, FMCAD 2002, Lecture Notes in Computer Science 2517 (2002), pp. 238–254] and extended to past time in [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)]: an initial phase involves putting LTL formulae into a normal form based on linear-time fixpoint characterisations of temporal operators.As with [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)] and [Latvala, T., A. Biere, K. Heljanko and T. Junttila, Simple bounded LTL model checking, in: Formal Methods in Computer-Aided Design; 5th International Conference, FMCAD 2004, Lecture Notes in Computer Science 3312 (2004), pp. 186–200], the size of propositional formulae produced is linear in the model checking bound, but the constant of proportionality appears to be lower.A denotational approach is taken in the presentation which is significantly more rigorous than that in [Frisch, A., D. Sheridan and T. Walsh, A fixpoint based encoding for bounded model checking, in: M.D. Aagaard and J.W. O'Leary, editors, Formal Methods in Computer-Aided Design; 4th International Conference, FMCAD 2002, Lecture Notes in Computer Science 2517 (2002), pp. 238–254] and [Cimatti, A., M. Roveri and D. Sheridan, Bounded verification of past LTL, in: A.J. Hu and A.K. Martin, editors, Proceedings of the 5th International Conference on Formal Methods in Computer Aided Design (FMCAD 2004), Lecture Notes in Computer Science (2004)], and which provides an elegant alternative way of viewing fixpoint based translations in [Latvala, T., A. Biere, K. Heljanko and T. Junttila, Simple bounded LTL model checking, in: Formal Methods in Computer-Aided Design; 5th International Conference, FMCAD 2004, Lecture Notes in Computer Science 3312 (2004), pp. 186–200] and [Biere, A., A. Cimatti, E. M. Clarke, O. Strichman and Y. Zhu, Bounded model checking, Advances in Computers 58 (2003)].