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:
“The basic idea which runs right through modern history and modern liberalism is that the public has got to be marginalized. The general public are viewed as no more than ignorant and meddlesome outsiders, a bewildered herd.”
—Noam Chomsky (b. 1928)
“American time has stretched around the world. It has become the dominant tempo of modern history, especially of the history of Europe.”
—Harold Rosenberg (1906–1978)
“The history of all countries shows that the working class exclusively by its own effort is able to develop only trade-union consciousness.”
—Vladimir Ilyich Lenin (1870–1924)