Constraint LTL satisfiability checking without automata

This paper introduces a novel technique to decide the satisfiability of formulae written in the language of Linear Temporal Logic with both future and past operators and atomic formulae belonging to constraint system DD (CLTLB(DD) for short). The technique is based on the concept of bounded satisfiability  , and hinges on an encoding of CLTLB(DD) formulae into QF-EUDD, the theory of quantifier-free equality and uninterpreted functions combined with DD. Similarly to standard LTL, where bounded model-checking and SAT-solvers can be used as an alternative to automata-theoretic approaches to model-checking, our approach allows users to solve the satisfiability problem for CLTLB(DD) formulae through SMT-solving techniques, rather than by checking the emptiness of the language of a suitable automaton. The technique is effective, and it has been implemented in our ZZot formal verification tool.