Verifying Systems with Continuous State Spaces

37 concepts46 papers1 proposal

Formal verification tools like model checkers traditionally operate on discrete, finite graphs. If a system has a finite number of configurations and transitions, a computer can exhaustively traverse them to prove safety or correctness.

But the real world is rarely discrete. Systems that interact with physical environments—such as autonomous vehicles, medical devices, and chemical networks—depend on continuous variables like time, velocity, voltage, or fluid levels. Because there are infinitely many real numbers between any two values (such as $t = 0.0$ and $t = 1.0$ seconds), the state space of these systems becomes uncountably infinite.

How can an algorithm exhaustively verify a system when it contains an infinite number of states? The answer lies in symbolic abstraction: partitioning an infinite continuum into a finite set of behaviorally equivalent regions.

The Tyranny of the Continuum

To understand why continuous variables break traditional verification, consider a real-time system where an action must occur within a strict deadline. As noted by Paul Pettersson et al. and Johan Bengtsson et al., tracking continuous time variables creates an infinite search space that prevents the direct application of standard finite-state exploration. You cannot simply step through time second by second, or even millisecond by millisecond, because critical system changes might occur at an arbitrary real-valued moment like $t = 0.4318...$ seconds.

This challenge extends far beyond clocks. Physical systems tracking continuous variables like voltage and current lack discrete Boolean logic, creating an infinite search space where a limited number of test observations cannot guarantee overall correctness (Peter Struss). Similarly, verifying scenario-based models that track physical metrics like a vehicle's velocity or heading involves handling an infinite number of possible data values (Guy Katz).

The Core Intuition: Equivalence Partitioning

The insight that makes verification possible is that while the state space is mathematically infinite, the system's qualitative behavior is usually uniform across large regions of that space.

Imagine a system that triggers an alarm if a temperature sensor exceeds 100°C. From the system's perspective, a temperature of 101.5°C and 102.5°C are functionally identical—both represent an unsafe state. We can therefore group the infinite continuum of temperatures into just two symbolic regions: $[-\infty, 100]$ (Safe) and $(100, +\infty]$ (Unsafe).

By proving that every individual point within a region shares the same transitions to subsequent regions, we can collapse an uncountably infinite graph into a finite, discrete graph. This finite representation can then be verified using standard model-checking algorithms.

Continuous Timeline:  0.0 -------------------> 1.0 ---------> 2.0 --->
                       |                        |              |
Symbolic Partition:   [      Region 1          )[   Region 2   )

Clock Zones and Timed Automata

This partitioning strategy is beautifully illustrated by Timed Automata, a foundational formalism for real-time systems. In a timed automaton, the system's state includes one or more continuous clock variables that advance at the exact same rate.

Paul Pettersson et al. demonstrated that instead of tracking exact clock values, verification tools can track linear inequalities between clocks (such as $x < 2$ and $y - x \ge 1$). These sets of inequalities form convex geometric shapes known as zones.

Because all clocks tick forward at identical speeds, the relative differences between them remain constant over time. This geometric regularity means that as time passes, a zone simply "slides" diagonally across a coordinate plane until it hits a boundary defined by a system transition or a reset. Consequently, an infinite timeline can be perfectly captured by a finite graph of these zones.

To scale this intuition to complex industrial systems, researchers developed specialized data structures. Gerd Behrmann et al. introduced Clock Difference Diagrams (CDDs) to efficiently store and manipulate these continuous zones, mitigating the state-space explosion problem.

This zone-based abstraction is highly versatile. For example, Masaki Waga et al. adapted zone abstractions to perform high-performance timed pattern matching on execution logs. By mapping continuous time constraints into discrete zones, the authors allowed string-matching algorithms to "skip" large sections of data logs without losing timing precision.

Abstracting Dynamical and Stochastic Systems

The principle of partitioning infinity applies equally well to complex physical systems governed by differential equations or stochastic uncertainty.

Switched Linear Systems

In cyber-physical systems, controllers switch between different continuous modes of operation (e.g., an automated cruise control accelerating versus braking). Ebru Aydin Gol et al. provided a method to construct finite bisimulations for these switched linear systems. A bisimulation is a discrete model that perfectly mirrors the transitions of the continuous system, allowing computer scientists to apply discrete model checking directly to physical control loops.

Stochastic Processes

When systems involve both continuous time and random behavior (like chemical reaction networks or communication protocols), tracking the exact evolution of continuous probability distributions is mathematically daunting.

To solve this, Sadegh Soudjani et al. introduced $\epsilon, \delta$-approximate similarity relations. Instead of forcing a perfect match between a continuous stochastic process and its finite abstraction, the authors allowed a bounded margin of error ($\epsilon$) with a specific probability confidence ($\delta$). This allows engineers to design and verify control policies on a simplified, finite model, and then safely refine those policies for the original continuous system with certified mathematical guarantees.

Similarly, Rupak Majumdar et al. abstracted continuous-state stochastic systems into finite-state games played against a "fair" adversary, allowing algorithms to compute tight bounds for complex temporal properties like liveness.

Alternative Paths to Finite Verification

While geometric partitioning (like clock zones) is common, researchers have developed other elegant mechanisms to bypass the continuum:

  • Automated Predicate Abstraction: Instead of manually defining regions, Bahareh Badban demonstrated how to automatically discover local invariants to map dense, real-time models directly to finite-state representations using logical predicates.
  • SMT Solvers: Rather than pre-calculating a finite graph, Guy Katz leveraged Satisfiability Modulo Theories (SMT) solvers to dynamically partition infinite data spaces on-the-fly, identifying safety violations and generating code patches automatically.
  • Barrier Functionals: For infinite-dimensional systems governed by Partial Differential Equations (PDEs), Mohamadreza Ahmadi et al. bypassed state exploration entirely. Using Sum of Squares (SOS) programming, the authors constructed mathematical "barrier functionals" that prove a system will never enter an unsafe state, providing a certified safety envelope without ever solving the underlying continuous equations.

Summary

Verifying systems with infinite state spaces works because continuity does not imply infinite behavioral diversity. By leveraging the geometric and algebraic regularities of time, physics, and probability, computer scientists can partition an uncountably infinite continuum into a finite set of symbolic regions. Whether through clock zones, bisimulations, or logical predicates, these abstractions bridge the gap between the continuous physical world and the discrete nature of computer logic.

Key Foundational Work

Compositional and Symbolic Model-Checking of Real-Time Systems (1996) — contributed 1 concept elements to this direction.
UPPAAL—a Tool Suite for Automatic Verification of Real–Time Systems (1996) — contributed 1 concept elements to this direction.
Testing Physical Systems (1994) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_infinite_state_space_verification_d8a4b157,
  title = {infinite state space verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-state-space-verification/rdr_d8a4b157923341589b9aca1775679d95},
  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_infinite_state_space_verification_d8a4b157_v1,
  title = {infinite state space verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/infinite-state-space-verification/rdr_d8a4b157923341589b9aca1775679d95/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake