Binary decision diagram

<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a binary decision diagram (BDD) or branching program is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> that is used to represent a <a href="/facts/Boolean_function/uT7E8pqC">Boolean function</a>. On a more abstract level, BDDs can be considered as a <a href="/facts/Data_compression/gMFuY4FT">compressed</a> representation of <a href="/facts/Set_(mathematics)/BfucfHMq">sets</a> or <a href="/facts/Relation_(mathematics)/HjblDaMy">relations</a>. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.
</p><p>Similar <a href="/facts/Data_structure/yNsNvL1I">data structures</a> include <a href="/facts/Negation_normal_form/A0tjapJz">negation normal form</a> (NNF), <a href="/facts/Zhegalkin_polynomial/etfekkPa">Zhegalkin polynomials</a>, and <a href="/facts/Propositional_directed_acyclic_graph/wPwQxRSJ">propositional directed acyclic graphs</a> (PDAG).
</p>

Binary decision diagram open-in-new

Binary decision diagram