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

v2 · 2026-09-06 · History

Domain-specific #

1262

Origin domain

computer science

Subdomain

formal methods

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.

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) — more general patterns this builds on

• 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 → Graph Data Type → Abstract Data Type → Information Hiding → Abstraction

Show alternative paths (3)

Neighborhood in Abstraction Space

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

Family — Discrete Structures & Graph Algorithms (17 abstractions)

Nearest neighbors

• Topological Sorting — 0.82
• Pathwidth — 0.82
• Monotonic Function — 0.81
• Friendly-index set — 0.80
• Boolean algebra — 0.80

Computed from structural-signature embeddings · 2026-09-08