Data structures for Boolean functions form an essential component of d
esign automation tools, especially in the area of logic synthesis. The
slate of the art data structure is the ordered binary decision diagra
m (OBDD), which results from general binary decision diagrams (BDDs),
also called branching programs, by the application of ordering restric
tions. In the context of EXOR-based logic synthesis another type of de
cision diagram (DD), called (ordered) functional decision diagram ((O)
FDD), becomes important. We study the relation between (ordered, free)
BDDs and FDDs. Both BDDs and FDDs result from DDs by defining the rep
resented function in different ways. If the underlying DD is complete,
the relation between these two types of interpretation can be describ
ed by a Boolean transformation tau. This allows us to relate the FDD-s
ize of f and the BDD-size of tau(f) also in the case where the corresp
onding DDs are free or ordered, but not (necessarily) complete. We use
this property to derive several results on the computational power of
OFDDs and OBDDs. Symmetric functions are shown to have efficient repr
esentations as OBDDs and OFDDs as well. Classes of functions are given
that have exponentially more concise OFDDs than OBDDs, and vice versa
. Finally, we determine the complexity of some standard operations if
OFDDs are used for the representation of Boolean functions. (C) 1995 A
cademic Press, Inc.