## 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