Editing Binary decision diagram (section)

== 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 (BDDs) were introduced by C. Y. Lee,<ref name="Lee"/> and further studied and made known by Sheldon B. Akers<ref name="Akers"/> and Raymond T. Boute.<ref name="Boute_1976"/> Independently of these authors, a BDD under the name "canonical bracket form" was realized Yu. V. Mamrukov in a CAD for analysis of speed-independent circuits.<ref>{{cite thesis |url=https://b-ok.asia/book/3701100/47f57d |first=Yu. V. |last=Mamrukov |title=Analysis of aperiodic circuits and asynchronous processes |type=PhD |publisher=Leningrad Electrotechnical Institute |date=1984}}</ref> 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.<ref name="Bryant-1986"/><ref name="Bryant-1992"/> 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.<ref name="Brace"/> 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)'',<ref name="Stanford"/> [[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.

[[Adnan Darwiche (computer scientist)|Adnan Darwiche]] and his collaborators have shown that BDDs are one of several normal forms for Boolean functions, each induced by a different combination of requirements. Another important normal form identified by Darwiche is [[decomposable negation normal form]] or DNNF.