Algebraic decision diagram

Last updated July 22, 2023

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.^[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

An ADD can be represented by a matrix according to its cofactors.^[2]^[1]

Applications

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

Related Research Articles

In mathematics, a binary relation associates elements of one set, called the domain, with elements of another set, called the codomain. A binary relation over sets $X$ and $Y$ is a new set of ordered pairs $(x, y)$ consisting of elements $x$ in $X$ and $y$ in $Y$ . It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element $x$ is related to an element $y$ , if and only if the pair $(x, y)$ belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case $n = 2$ of an $n$ -ary relation over sets $X 1, ..., X n$ , which is a subset of the Cartesian product

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

In mathematics, the power set (or powerset) of a set $S$ is the set of all subsets of $S$ , including the empty set and $S$ itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postulated by the axiom of power set. The powerset of $S$ is variously denoted as $P (S)$ , $𝒫(S)$ , $P (S)$ , $,, or 2 S . The notation 2 S, meaning the set of all functions from S to a given set of two elements (e.g., {0, 1}), is used because the powerset of S can be identified with, equivalent to, or bijective to the set of all the functions from S to the given two elements set.$

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In computer science, a binary decision diagram (BDD) or branching program is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations. Unlike other compressed representations, operations are performed directly on the compressed representation, i.e. without decompression.

In electrical engineering and electronics, a network is a collection of interconnected components. Network analysis is the process of finding the voltages across, and the currents through, all network components. There are many techniques for calculating these values; however, for the most part, the techniques assume linear components. Except where stated, the methods described in this article are applicable only to linear network analysis.

A binary moment diagram (BMD) is a generalization of the binary decision diagram (BDD) to linear functions over domains such as booleans (like BDDs), but also to integers or to real numbers.

A zero-suppressed decision diagram is a particular kind of binary decision diagram (BDD) with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the Ordered Binary Decision Diagram (OBDD) reduction strategy, i.e. a node is replaced with one of its children if both out-edges point to the same node. In contrast, a node in a ZDD is replaced with its negative child if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin-ichi Minato in 1993.

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2^X² of all binary relations on a set X, that is, subsets of the cartesian square X², with R•S interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation.

A propositional directed acyclic graph (PDAG) is a data structure that is used to represent a Boolean function. A Boolean function can be represented as a rooted, directed acyclic graph of the following form:

<span class="mw-page-title-main">And-inverter graph</span> Graph representing an implementation of the logical functionality of a network

An and-inverter graph (AIG) is a directed, acyclic graph that represents a structural implementation of the logical functionality of a circuit or network. An AIG consists of two-input nodes representing logical conjunction, terminal nodes labeled with variable names, and edges optionally containing markers indicating logical negation. This representation of a logic function is rarely structurally efficient for large circuits, but is an efficient representation for manipulation of boolean functions. Typically, the abstract graph is represented as a data structure in software.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible input length.

Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit design.

In mathematics, an approximately finite-dimensional (AF) C*-algebra is a C*-algebra that is the inductive limit of a sequence of finite-dimensional C*-algebras. Approximate finite-dimensionality was first defined and described combinatorially by Ola Bratteli. Later, George A. Elliott gave a complete classification of AF algebras using the K₀ functor whose range consists of ordered abelian groups with sufficiently nice order structure.

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables. In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.

A binary decision is a choice between two alternatives, for instance between taking some specific action or not taking it.

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 variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and the negation (not) denoted as ¬. Elementary algebra, on the other hand, uses arithmetic operators such as addition, multiplication, subtraction and division. Boolean algebra is therefore a formal way of describing logical operations, in the same way that elementary algebra describes numerical operations.

References

1 2 3 4 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.
1 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. 10 (2): 149–169. doi:10.1023/A:1008647823331. ISSN 1572-8102. S2CID 30494217.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:1-1] 1 2 3 4 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.

[:0-2] 1 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. 10 (2): 149–169. doi:10.1023/A:1008647823331. ISSN 1572-8102. S2CID 30494217.

[1]

[2]