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:
“We said that the history of mankind depicts man; in the same way one can maintain that the history of science is science itself.”
—Johann Wolfgang Von Goethe (1749–1832)
“If usually the “present age” is no very long time, still, at our pleasure, or in the service of some such unity of meaning as the history of civilization, or the study of geology, may suggest, we may conceive the present as extending over many centuries, or over a hundred thousand years.”
—Josiah Royce (1855–1916)
“I am ashamed to see what a shallow village tale our so-called History is. How many times must we say Rome, and Paris, and Constantinople! What does Rome know of rat and lizard? What are Olympiads and Consulates to these neighboring systems of being? Nay, what food or experience or succor have they for the Esquimaux seal-hunter, or the Kanaka in his canoe, for the fisherman, the stevedore, the porter?”
—Ralph Waldo Emerson (1803–1882)