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]
Binary decision diagram Created 2026-10-31 Updated 2026-11-05
A directed acyclic graph representing a Boolean function. A decision node tests a Boolean variable and has zero and one successors; evaluation follows the corresponding arrows until a terminal node returns a Boolean value. Sharing subgraphs can make a binary decision diagram much smaller than a binary decision tree.
Decision node 2026-10-31
An internal vertex that tests a condition and selects an outgoing branch. In a binary decision diagram, a decision node tests a Boolean variable and has one zero arrow and one one arrow.
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]
Ordered binary decision diagram Created 2026-10-31 Updated 2026-11-05
An ordered binary decision diagram is a binary decision diagram using one fixed variable ordering of a binary decision diagram along every root-to-terminal branch. Tests may be omitted, but no branch may test a later variable before an earlier one. For the order , a branch testing is permitted; a branch testing is not. Sharing equal residual Boolean functions can compress the diagram. Applying the reduction rules gives a reduced ordered binary decision diagram, canonical for the chosen order; a different order can have a dramatically different size.
Solutions to the paper whose cover dates the examination to 6 June 2015, 2:30–4:00 pm. Source: released examination archive, member
2015-cafv.pdf. All three questions are covered, although candidates were asked to attempt at most two. In the binary decision diagrams, dashed arrows mean zero and solid arrows mean one. In the linear temporal logic calculations, , and .Follow the binary decision diagram from its top decision node to a terminal node, choosing the outgoing arrow specified by each tested Boolean variable. If , the left decision node returns , independently of . If , the right decision node returns one when and otherwise returns . Thus the truth table, with rows in the order , is:
Thus the output column of the truth table, in the displayed order, is . In particular, the skipped test on the left does not constrain : both values give the same result.
A reduced ordered binary decision diagram is obtained by sharing equal terminal nodes, removing a decision node whose two children are equal, and sharing decision nodes with the same tested Boolean variable and the same ordered pair of children. Apply these rules to the binary decision tree in part (c) as follows.
- Merge the three zero terminal nodes into one zero terminal node, and merge the five one terminal nodes into one one terminal node.
- At the decision node has children . Remove it and redirect its incoming arrow to zero.
- At and the two decision nodes each have children . Remove both and redirect their incoming arrows to one.
- The remaining decision node, at , has children , so retain it.
- The decision node under now has children , while the one under has children . These are different, so neither can be merged or removed. The top decision node also has different children.
The left panel below is therefore the resulting reduced ordered binary decision diagram. Its full description is
Reduced ordered decision diagrams: reversing the given order preserves its size, while testing y first saves one decision node
. Details. The original binary decision diagram also has four decision nodes and two terminal nodes, and is already reduced for : the two decision nodes have different children and no decision node has two equal children. Thus reversing the order has not made this example smaller. Indeed is unchanged by interchanging and , and the new binary decision diagram is the original one with those two labels exchanged. The uniqueness of a reduced ordered binary decision diagram applies to a fixed variable ordering of a binary decision diagram; it does not assert that every ordering has the same size.
Choose the variable ordering of a binary decision diagram . The Boolean cofactor with is the constant one, while the Boolean cofactor with is . Consequently the right panel in part (d) has the following arrows:Here an entry such as denotes the zero arrow to the decision node. There are vertices: three decision nodes and two terminal nodes, saving one decision node relative to either of the previous orderings. Testing first is effective because its one branch settles the entire Boolean function immediately. The ordering works equally well.
This is also minimal among ordinary binary decision diagrams for this Boolean function. Each Boolean variable is essential: setting leaves ; setting leaves ; and setting leaves . If a Boolean variable were never tested, the represented Boolean function could not depend on it. Thus at least three decision nodes are necessary, and the construction attains that bound.
Reduced ordered binary decision diagram 2026-10-31
An ordered binary decision diagram with shared equal terminal nodes, no decision node having identical zero and one children, and no two decision nodes having the same tested Boolean variable and the same ordered pair of children. For a fixed variable ordering of a binary decision diagram, it is unique up to labelled graph isomorphism: each nonconstant remaining Boolean cofactor has a uniquely determined first essential Boolean variable, and its two children are recursively determined by its zero and one Boolean cofactors. This uniqueness does not compare different orderings.
Symbolic model checking 2026-11-05
Symbolic model checking verifies a Transition system by representing sets of states and transitions as formulas or decision structures rather than enumerating each state separately. Encode a current state by bits and its successor by bits . A formula describes the transition relation. If denotes currently reachable states, the next reachable set isIterating from the initial-state formula reaches a fixed point in a finite system. Intersecting that set with a bad-state formula checks a safety property.
Binary decision diagrams can make these operations compact when the represented Boolean structure is favorable. A system with Boolean state components has up to states, so sharing structure can be decisive. The representation can nevertheless become exponentially large, and variable ordering strongly affects a decision diagram's size. Symbolic representation mitigates state-space explosion; it does not abolish it.
Terminal node 2026-10-31
A fixed order in which Boolean variables may be tested along each branch of an ordered binary decision diagram. Branches may skip a test, but cannot reverse the order. The order can change the number of distinct remaining Boolean cofactors and therefore the size of the representation.
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]
