Questions: BDD-Based Verification

Question 1

Why does representing state sets as BDDs overcome the state explosion problem that limits explicit-state model checking?

• A. BDDs use compression to store each state in fewer bits
• B. BDDs represent sets of states as Boolean functions over state variables, and many structured sets that are exponentially large when enumerated have polynomial-size BDD representations. Set operations (union, intersection, image computation) are performed directly on BDDs without unpacking individual states
• C. BDDs eliminate unreachable states during construction
• D. BDDs parallelize the search across multiple processors

Answer: (B)

The key insight is that many state sets arising in practice have compact BDD representations even when they contain exponentially many states. A set like 'all states where variable x equals variable y' over 64-bit variables contains 2^64 states but has a linear-size BDD. Set union, intersection, complement, and existential quantification (used for transition image computation) are all BDD operations with polynomial complexity in BDD size. This lets the model checker reason about huge state sets implicitly.

Question 2

The size of a BDD for a Boolean function depends heavily on the variable ordering, and finding the optimal ordering is NP-hard.

• T. True
• F. False

Answer: True

The same Boolean function can have a BDD that is linear in the number of variables under one ordering and exponential under another. For example, the function x1*y1 + x2*y2 + ... + xn*yn (bitwise comparison) has O(n) nodes with interleaved ordering (x1,y1,x2,y2,...) but O(2^n) nodes with separated ordering (x1,x2,...,y1,y2,...). Finding the optimal variable ordering is NP-hard, so practical tools use heuristics (sifting, symmetry detection) and domain-specific ordering strategies.

Question 3

Explain how BDD-based model checking computes the set of states reachable from the initial states of a Kripke structure.

Model answer: Start with the BDD representing the initial state set I. In each iteration, compute the image: apply the transition relation (also a BDD over current-state and next-state variables) to the current reachable set, existentially quantifying out the current-state variables to obtain the set of next states. Take the union with the current reachable set. Repeat until a fixed point — the reachable set stops growing. All operations (image computation, union, fixed-point check) are BDD operations, never enumerating individual states.

This fixed-point computation is the core of symbolic model checking. The transition relation R(s, s') is encoded as a BDD over 2n Boolean variables (n for current state, n for next state). The image of a set S is computed as: exists s. (S(s) AND R(s,s')), yielding a BDD over next-state variables representing all possible successors. Renaming next-state variables back to current-state variables and taking the union with S gives the new reachable set. Convergence is guaranteed because the state space is finite.