Symbolic State Space Representation with Decision Diagrams

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2205 papers284 conceptsfrozen 2026-10-04

In fields like automated planning, formal verification, and reactive synthesis, researchers face a common enemy: the "state space explosion." As systems grow in complexity—adding more variables, agents, or possible actions—the number of possible configurations grows exponentially. Traditional "explicit" methods, which track and visit states one by one, quickly exhaust memory and time.

To overcome this, a broad research direction has emerged around symbolic representation. Instead of enumerating individual states, these methods represent entire sets of states and transition relations as compact mathematical structures, most notably Binary Decision Diagrams (BDDs). By treating state sets as boolean functions, researchers can manipulate billions of states simultaneously.

From Individual States to Boolean Functions

The core intuition behind symbolic methods is that many states in a system share structural similarities. In an explicit search, if two states differ by only one variable, they are still stored as two distinct entries. In a symbolic representation, these states are grouped.

As Alessandro Cimatti, Marco Roveri, and Paolo Traverso demonstrated in Automatic OBDD-Based Generation of Universal Plans in Non-Deterministic Domains, we can encode a set of states as a boolean formula. A Binary Decision Diagram then serves as a canonical, compressed representation of that formula. This allows for "planning via model checking," where the search for a solution becomes an operation on logic gates rather than a traversal of a graph.

Jussi Rintanen further applied this to Conditional Planning in the Discrete Belief Space, showing that BDDs can bypass the exponential branching typical of forward-search planners by performing backward search over sets of belief states.

Scaling to Billions of States

The power of symbolic representation is most evident in verification. Marta Kwiatkowska and David Parker have shown in Advances in Probabilistic Model Checking that symbolic data structures enable the exhaustive verification of models containing billions of states.

This is achieved through several specialized variants of the decision diagram:

Synthesis and Reactive Systems

Beyond just checking if a system works, symbolic methods are used to build systems that are correct by construction. This is known as reactive synthesis. In the The Reactive Synthesis Competition (SYNTCOMP), researchers like Guillermo Perez and Michaël Cadilhac have tracked the dominance of BDD-based solvers.

Tools like Strix and LISA use symbolic representations to handle the high theoretical complexity of Linear Temporal Logic (LTL) synthesis. For example, LISA employs a hybrid approach, using explicit-state representations for small components and switching to symbolic BDDs once a state-space threshold is reached. This allows the tool to minimize small automata efficiently while still scaling to massive systems.

Beyond Boolean Logic: Continuous and Infinite Systems

The reach of symbolic representation extends into continuous and infinite-state domains. Majid Zamani and Alessandro Abate demonstrated in Symbolic Models for Networked Control Systems that BDDs can encode transition relations for high-dimensional physical models, making formal controller synthesis practical for systems previously limited by the "curse of dimensionality."

Similarly, in Parameterized Verification of Infinite-State Processes with Global Conditions, Parosh Aziz Abdulla and colleagues showed that symbolic grouping can verify distributed algorithms with an unbounded number of processes in seconds, proving that structural redundancy is the key to taming even infinite state spaces.

Papers in this version

Showing 60 of 205 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 197 papers
  2. Version 1 · 2026-10-04 · 205 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_symbolic_state_representation_symbolic_s_aa5abd20,
  title = {symbolic state representation (symbolic state space representation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-state-representation-symbolic-state-space-representation/rdr_aa5abd204e224c6d8b4f3a03459585fb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_symbolic_state_space_representation_with_aa5abd20_v1,
  title = {Symbolic State Space Representation with Decision Diagrams},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-state-space-representation-with-decision-diagrams/rdr_aa5abd204e224c6d8b4f3a03459585fb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}