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 In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

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). The terminal nodes may take any value from a set of constants S.

Definition

An ADD represents a Boolean function from

\^n

to a finite set of constants S, or carrier of the

algebraic structure In mathematics, an algebraic structure or algebraic system consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplicatio ...

. 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 In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...

, by extending the codomain of the function, such that

f: \^n \to Q

with

S \subseteq Q

and

card(Q) = 2^n

for some integer n. Therefore, the theorems of the

Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variable (mathematics), variables are the truth values ''true'' and ''false'', usually denot ...

applies to ADD, notably the

Boole's expansion theorem Boole's expansion theorem, often referred to as the Shannon expansion or decomposition, is the identity: F = x \cdot F_x + x' \cdot F_, where F is any Boolean function, x is a variable, x' is the complement of x, and F_xand F_ are F with the argume ...

. 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 In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...

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 In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

( Bellman-Ford, Repeated Squaring, and Floyd-Warshall procedures).

References

{{Reflist Diagrams Graph data structures

Definition

Matrix partitioning

Applications

See also

References