Choose which of four tools computes its results with BDDs.
A BDD-based engine represents sets of states and transition relations as decision diagrams, and computes with operations on them, such as Apply and quantification, as Modules 3 and 7 do. A SAT-based engine instead hands formulas to a SAT solver and learns clauses from its answers. One tool can offer engines of both kinds, so the question is which data structure a given engine computes with.
The NuSMV model checker offers two engines: BDD-based symbolic model checking, and SAT-based bounded model checking (Cimatti et al., 2002).
Its BDD engine computes images, as Module 7 does: for a 1-bit register s that toggles on each clock, with next state n, the image of ~s is exists s. ~s & (n ~^ ~s), which is n.
s
n
~s
exists s. ~s & (n ~^ ~s)
Its bounded engine instead unrolls the design for a fixed number of clock cycles into one formula, and asks a SAT solver whether a bad state is reachable within them.
So NuSMV's symbolic engine computes with BDDs, and its bounded engine does not.
Which of these computes its results with BDDs?
PRISM's MTBDD and hybrid engines, for probabilistic models (PRISM manual).
rIC3, the winner of the 2024 hardware model checking competition (Froleyks et al., 2025).
ABC's pdr command (Eén et al., 2011).
A CDCL SAT solver's clause learning.
Choose one of the four options. Each named engine links its source.
One answer.
For each option, ask which data structure it computes with, as the example asks of NuSMV's two engines.
Where you are unsure, read the option's source: it says what the engine is built on.
Kata 8.4 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.