History
The basic idea from which the data structure was created is the Shannon expansion. A switching function is split into two sub-functions (cofactors) by assigning one variable (cf. if-then-else normal form). If such a sub-function is considered as a sub-tree, it can be represented by a binary decision tree. Binary decision diagrams (BDD) were introduced by Lee, and further studied and made known by Akers and Boute.
The full potential for efficient algorithms based on the data structure was investigated by Randal Bryant at Carnegie Mellon University: his key extensions were to use a fixed variable ordering (for canonical representation) and shared sub-graphs (for compression). Applying these two concepts results in an efficient data structure and algorithms for the representation of sets and relations. By extending the sharing to several BDDs, i.e. one sub-graph is used by several BDDs, the data structure Shared Reduced Ordered Binary Decision Diagram is defined. The notion of a BDD is now generally used to refer to that particular data structure.
In his video lecture Fun With Binary Decision Diagrams (BDDs), Donald Knuth calls BDDs "one of the only really fundamental data structures that came out in the last twenty-five years" and mentions that Bryant's 1986 paper was for some time one of the most-cited papers in computer science.
Read more about this topic: Binary Decision Diagram
Famous quotes containing the word history:
“America is, therefore the land of the future, where, in the ages that lie before us, the burden of the World’s history shall reveal itself. It is a land of desire for all those who are weary of the historical lumber-room of Old Europe.”
—Georg Wilhelm Friedrich Hegel (1770–1831)
“Considered in its entirety, psychoanalysis won’t do. It’s an end product, moreover, like a dinosaur or a zeppelin; no better theory can ever be erected on its ruins, which will remain for ever one of the saddest and strangest of all landmarks in the history of twentieth-century thought.”
—Peter B. Medawar (1915–1987)
“Systematic philosophical and practical anti-intellectualism such as we are witnessing appears to be something truly novel in the history of human culture.”
—Johan Huizinga (1872–1945)