Alessandro Cimatti Created 2026-10-31 Updated 2026-11-05
Alessandro Cimatti coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
Armin Biere Created 2026-10-31 Updated 2026-11-05
Armin Biere coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
Edmund Clarke Created 2026-10-31 Updated 2026-11-05
Edmund Clarke coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]
To apply bounded model checking, seek an initial path in a transition system satisfying
A satisfying assignment for its bounded encoding is enough to disprove the specification. Use a lasso path: positions follow the transition relation, and a final arrow returns from to some , . The repeated part is . On such a lasso path, is equivalent to having true at some position of the repeated part.
For this example an explicit Boolean formula for the bounded search is
Here means and means that the source diagram has the arrow ; each can be encoded by finite Boolean variables for the states. The loop requirements are the fairness assumption and the negated specification respectively. Unrolling the transition relation and adding a loop closure is the usual bounded model checking construction.[ref]
At bound , an initial self-loop would be needed. The only such choice is , whose repeated label satisfies and . It violates both loop requirements. The other initial state, , has no self-loop. Thus has no satisfying assignment.
At bound , choose
Both required arrows and exist. At , is false and hence is false, so both repeated-part requirements are true. Equivalently, the label values are and . These values give a satisfying assignment of , representing the fair counterexample . Consequently
Here the bound counts forward arrows before the returning arrow, so stores two positions and describes a two-state repeated part. There is no need for a completeness bound: the exhibited fair counterexample settles the negative answer. These satisfying assignments are checked directly; no claim of executing an external SAT solver is needed.
By Armin Biere, Alessandro Cimatti, Edmund Clarke and Yunshan Zhu. Published in Tools and Algorithms for the Construction and Analysis of Systems, volume 1579, pp. 193–207.
Introduces bounded model checking by translating a search for a bounded counterexample into a Boolean satisfiability problem. Section 2 explains unrolling and loop closure through a worked example; §3 states infinite-path semantics; §4 gives the encoding; §5 discusses bounds.
Yunshan Zhu Created 2026-10-31 Updated 2026-11-05
Yunshan Zhu coauthored Symbolic Model Checking without BDDs by Armin Biere and others, which introduced a bounded model checking procedure for linear temporal logic using Boolean satisfiability. The method encodes a finite sequence of finite-state machine transitions as a propositional formula; a satisfying assignment can describe a path violating a requested property. The paper demonstrates how SAT solving can replace binary decision diagrams in this verification task.[ref]