Symbolic model checking, based mostly on BDD graphs, is a standard technology nowadays. It has been implemented in several tools like Uppaal, Kronos, RED, or Cadence FORMALCHECK. In the last decade, very efficient implementations of SAT solvers have been provided. Thanks to that SAT-based Bounded Model Checking (BMC) and Unbounded Model Checking (UMC) became feasible. The idea of UMC [4] consists in encoding the states of a model, where a temporal formula holds, by propositional formulas in conjunctive normal form (called blocking clauses). Unfortunately, the number of these clauses can be exponential. There are several methods aiming at improving the above deficiency by using generalized blocking clauses [6], or for instance circuit cofactoring [3]. In this paper we define and use timed generalized blocking clauses in UMC of timed automata for untimed temporal properties expressed in CTL_X.
Citation:
Wojciech Penczek, Maciej Szreter, "SAT-based Unbounded Model Checking of Timed Automata," acsd, pp.236-237, Seventh International Conference on Application of Concurrency to System Design (ACSD 2007), 2007