Algebraic decision diagram explained

An algebraic decision diagram (ADD) or a multi-terminal binary decision diagram (MTBDD), is a data structure that is used to symbolically represent a Boolean function whose codomain is an arbitrary finite set S. An ADD is an extension of a reduced ordered binary decision diagram, or commonly named binary decision diagram (BDD) in the literature, which terminal nodes are not restricted to the Boolean values 0 (FALSE) and 1 (TRUE).^{[1] [2]} The terminal nodes may take any value from a set of constants S.

Definition

An ADD represents a Boolean function from

\{ 0 , 1 \} ^{n} to a finite set of constants S, or carrier of the algebraic structure. An ADD is a rooted, directed, acyclic graph, which has several nodes, like a BDD. However, an ADD can have more than two terminal nodes which are elements of the set S, unlike a BDD.

An ADD can also be seen as a Boolean function, or a vectorial Boolean function, by extending the codomain of the function, such that

f: \{ 0 , 1 \} ^{n} \to Q with S \subseteq Q and card(Q) = 2 ^{n} for some integer n. Therefore, the theorems of the Boolean algebra applies to ADD, notably the Boole's expansion theorem.

Each node of is labeled by a Boolean variable and has two outgoing edges: a 1-edge which represents the evaluation of the variable to the value TRUE, and a 0-edge for its evaluation to FALSE.

An ADD employs the same reduction rules as a BDD (or Reduced Ordered BDD):

• merge any isomorphic subgraphs, and
• eliminate any node whose two children are isomorphic.

ADDs are canonical according to a particular variable ordering.

Matrix partitioning

An ADD can be represented by a matrix according to its cofactors.

Applications

ADDs were first implemented for sparse matrix multiplication and shortest path algorithms (Bellman-Ford, Repeated Squaring, and Floyd-Warshall procedures).

See also

• Binary decision diagram
• Zero-suppressed decision diagram

Notes and References

1. Book: Bahar . R.I. . Frohm . E.A. . Gaona . C.M. . Hachtel . G.D. . Macii . E. . Pardo . A. . Somenzi . F. . Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) . Algebraic decision diagrams and their applications . https://doi.org/10.1109/ICCAD.1993.580054 . 1993 . 188–191 . en-US . IEEE Comput. Soc. Press . 10.1109/iccad.1993.580054. 0-8186-4490-7 . 43177472 .
2. Fujita . M. . McGeer . P.C. . Yang . J.C.-Y. . 1997-04-01 . Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation . Formal Methods in System Design . en . 10 . 2 . 149–169 . 10.1023/A:1008647823331 . 30494217 . 1572-8102.