Algebraic Decision Diagram¶

A reduced ordered binary decision DAG whose terminal nodes carry values from a finite domain not restricted to Boolean values, canonically representing a multivalued function for a fixed variable order.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1262
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomain: Formal Methods → Computer Science & Software Engineering
Aliases: ADD, Multi-terminal binary decision diagram, MTBDD

Core Idea¶

An algebraic decision diagram (ADD), also called a multi-terminal binary decision diagram (MTBDD), is a rooted directed acyclic graph that compactly represents a function

\[ f:\{0,1\}^n\longrightarrow S, \]

where \(S\) is a finite set of terminal values rather than only the Boolean values false and true. Each internal node tests one Boolean variable and has a low edge for value zero and a high edge for value one. Following edges under an input assignment reaches a terminal carrying the function value. A fixed variable order constrains the order in which variables may appear along every root-to-terminal path.

How would you explain it like I'm…

The Question Path to a Number

Think of a game where you answer yes-or-no questions, one after another, and each answer sends you down a different path. At the end of the path you find a number, not just 'yes' or 'no'. If two paths would lead to exactly the same rest of the game, the drawing uses just one copy to save space. That kind of question map is an algebraic decision diagram.

Question Flowchart With Number Endings

An algebraic decision diagram, or ADD, is a map for looking up a value from a list of on/off switches. Each circle in the map asks about one switch: if it's off you follow one arrow, if it's on you follow the other. You always ask about switches in the same fixed order. When you reach the end, you land on a box holding a value, which can be one of several numbers, not only true or false. The diagram saves space by merging parts that are exactly the same and removing questions whose answer doesn't matter, and after that tidying, each function has just one possible diagram.

Multi-Terminal Decision Diagram

An algebraic decision diagram (ADD), also called a multi-terminal binary decision diagram (MTBDD), is a directed acyclic graph that represents a function from n Boolean inputs to a finite set of values. Each internal node tests one variable and has a low edge (variable = 0) and a high edge (variable = 1); following the edges for a given input leads to a terminal node holding the function's value. Variables must appear in a fixed order along every path. Like reduced ordered binary decision diagrams (BDDs), ADDs are simplified by merging identical subgraphs and deleting nodes whose two edges go to the same place. With a fixed variable order, this reduced form is canonical: two functions are equal exactly when their reduced diagrams are the same shape. The difference from a BDD is only at the leaves, which can hold many values instead of just true and false; 'algebraic' refers to those leaf values and the operations on them, not to algebraic geometry.

An algebraic decision diagram (ADD), or multi-terminal BDD, is a rooted DAG representing f: {0,1}^n → S for a finite terminal set S. Internal nodes test a single Boolean variable with low (0) and high (1) successors, evaluation follows the path selected by an assignment to a terminal carrying f's value, and a fixed variable order constrains the order of tests on every root-to-terminal path. ADDs inherit the reduction rules of reduced ordered BDDs: merge isomorphic subgraphs and eliminate any internal node whose low and high successors coincide. Under a fixed ordering and terminal interpretation, the reduced diagram is canonical, so equivalent functions have isomorphic reduced diagrams, which makes the ADD both a compact value table and a manipulable symbolic object for equality checks and operations. 'Algebraic' refers to the terminal carrier and its operations; the original literature develops a Boolean-algebra-based treatment with applications including matrix multiplication, shortest paths, and numerical linear algebra. The concept is narrower than an arbitrary decision DAG, since inputs remain binary with ordering and reduction, and broader than a BDD, since the range admits several constants.

Scope of Application¶

ADDs are useful where a large indexed table contains repeated substructure. A matrix indexed by Boolean encodings of row and column numbers can be represented by a diagram whose terminals are entries. Weighted transition systems and probabilistic models can store probabilities or rewards at leaves. Model checking can combine diagrams symbolically instead of enumerating every state. The original research also describes direct numerical linear algebra and shortest-path computations.

Clarity¶

The word “decision” can mislead. The graph need not encode a human or optimization decision; its nodes select a cofactor according to a Boolean input. Likewise, the high and low edges do not themselves carry probability or preference. They mean assignment values one and zero.

Two conditions must accompany any canonicity claim: variable order and reduction. An unreduced diagram can denote the same function in many shapes.

Manages Complexity¶

A complete truth-style table for \(n\) Boolean variables has \(2^n\) entries. The ADD replaces repeated rows, columns, or cofactors with shared subgraphs. Reduction performs two distinct compressions: merging isomorphic subgraphs removes repeated computation, while deleting redundant tests removes variables that do not affect a subfunction. Dynamic programming can then operate once per unique subgraph rather than once per assignment.

Abstract Reasoning¶

ADD reasoning follows Shannon decomposition. At a node testing \(x\), a function is divided into the low cofactor \(f|_{x=0}\) and high cofactor \(f|_{x=1}\). Recursive operations align variables, combine corresponding cofactors, and reduce the result. This gives a uniform “apply” pattern for pointwise operations on represented functions when the terminal operation is defined.

Knowledge Transfer¶

The binary decision diagram toolkit transfers directly: ordered tests, Shannon expansion, unique-node interning, reduction, apply algorithms, and sensitivity to variable order. The change is concentrated at terminals, where Boolean truth values are replaced with elements of \(S\). This permits BDD engineering lessons to transfer while making range-specific arithmetic explicit.

Matrix encodings illustrate another transfer. Boolean bits can encode row and column indices; recursively partitioning a matrix becomes the same operation as taking cofactors of an indexed function. Repeated blocks then become shared subgraphs.

Relationships to Other Abstractions¶

Current abstraction Algebraic Decision Diagram Domain-specific

Parents (1) — outgoing typed relations

Algebraic Decision Diagram is a kind of Graph Data Type Domain-specific

domain_specific:graph_data_type is the immediate representational parent: an ADD is a specialized directed graph data structure with a strict node/edge API and semantics.

Hierarchy paths (4) — routes to 3 parentless roots

Algebraic Decision Diagram → is a kind of Graph Data Type → is a kind of Abstract Data Type → presupposes, typical Information Hiding → is a kind of, typical Abstraction

Show alternative paths (3)

Neighborhood in Abstraction Space¶

Algebraic Decision Diagram sits in a sparse region of the domain-specific corpus (85^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25