Differential BDD's

Anuchit Anuchitanukul, Zohar Manna Tomas Uribe,

We present a class of Ordered Binary Decision Diagram, Differential BDDs (Delta-BDDs), and transformations Push-up and Delta over them. In addition to the ordinary node-sharing in normal BDDs, isomorphic substructures can be collapsed further in Delta-BDDs and their derived classes, forming a more compact representation of boolean functions. The elimination of isomorphic substructures coincides with the repetitive occurrences of small components in many applications of BDDs. The reduction is potentially exponential in the number of nodes and proportional to the number of variables, while operations on Delta-BDDs remain efficient.

In J. van Leeuwen, ed, Computer Science Today , Lecture Notes in Computer Science, Vol. 1000, pp. 218-233, Springer-Verlag, Sep. 1995.

Postscript, PDF. © 1995, Springer Verlag.


© Henny Sipma / sipma@cs.stanford.edu
Last modified: Thu Mar 29 22:06:59 PST 2001