algebraic decision diagram
{{Short description|Symbolic boolean function representation, extension of BDDs}}
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).{{Cite book |last1=Bahar |first1=R.I. |last2=Frohm |first2=E.A. |last3=Gaona |first3=C.M. |last4=Hachtel |first4=G.D. |last5=Macii |first5=E. |last6=Pardo |first6=A. |last7=Somenzi |first7=F. |title=Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) |chapter=Algebraic decision diagrams and their applications |chapter-url=https://doi.org/10.1109/ICCAD.1993.580054 |year=1993 |pages=188–191 |language=en-US |publisher=IEEE Comput. Soc. Press |doi=10.1109/iccad.1993.580054|isbn=0-8186-4490-7 |s2cid=43177472 }}{{Cite journal |last1=Fujita |first1=M. |last2=McGeer |first2=P.C. |last3=Yang |first3=J.C.-Y. |date=1997-04-01 |title=Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation |url=https://doi.org/10.1023/A:1008647823331 |journal=Formal Methods in System Design |language=en |volume=10 |issue=2 |pages=149–169 |doi=10.1023/A:1008647823331 |s2cid=30494217 |issn=1572-8102}} The terminal nodes may take any value from a set of constants S.
Definition
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.
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
Applications
ADDs were first implemented for sparse matrix multiplication and shortest path algorithms (Bellman-Ford, Repeated Squaring, and Floyd-Warshall procedures).