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 edit
An ADD represents a Boolean function from 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 with and for some integer n. Therefore, the theorems of the Boolean algebra applies to ADD, notably the Boole's expansion theorem.[1]
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 partitionning edit
An ADD can be represented by a matrix according to its cofactors.[2][1]
Applications edit
ADDs were first implemented for sparse matrix multiplication and shortest path algorithms (Bellman-Ford, Repeated Squaring, and Floyd-Warshall procedures).[1]
See also edit
References edit
- ^ a b c d Bahar, R.I.; Frohm, E.A.; Gaona, C.M.; Hachtel, G.D.; Macii, E.; Pardo, A.; Somenzi, F. (1993). "Algebraic decision diagrams and their applications". Proceedings of 1993 International Conference on Computer Aided Design (ICCAD). IEEE Comput. Soc. Press. pp. 188–191. doi:10.1109/iccad.1993.580054. ISBN 0-8186-4490-7. S2CID 43177472.
- ^ a b 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. 10 (2): 149–169. doi:10.1023/A:1008647823331. ISSN 1572-8102. S2CID 30494217.