💻 computer science

Symbolic Model Checking using Intervals of Vectors

This paper introduces a novel symbolic model checking method for Petri nets that utilizes generalised intervals on vectors to overcome state space explosion, demonstrating promising performance on global CTL verification tasks through efficient saturation and clustering techniques.

Original authors: Damien Morard, Lucas Donati, Didier Buchs

Published 2026-02-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Damien Morard, Lucas Donati, Didier Buchs

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Infinite Library"

Imagine you are trying to check if a library follows a specific rule, like "No one can have more than 5 books at once." In a small library, you could just walk down every aisle and count the books on every shelf. This is called Model Checking.

However, in computer science, systems (like software or traffic lights) are like massive libraries with infinite aisles. The number of possible states (how many books are on every shelf) grows so fast that it becomes impossible to count them one by one. This is the famous "State Space Explosion" problem. If you try to list every single possibility, your computer will run out of memory before it finishes.

The Old Way: The "List of Ranges"

To solve this, researchers usually use Decision Diagrams. Think of this like organizing a library not by listing every book, but by creating a giant, multi-layered map.

The Paper's Critique: The authors say existing methods are like having a list of "Intervals" (e.g., "Books 1 to 10," "Books 20 to 30"). But when you have multiple shelves (dimensions) at once, these lists get messy. It's like trying to describe a 3D room using only 1D lines; it doesn't fit well.

The New Idea: "Vector Intervals"

The authors propose a new way to organize the library called Symbolic Vector Sets.

The Analogy: The "Inclusion and Exclusion" Box
Imagine you want to describe a group of people in a room without naming them individually.

Old Way: You might say, "Everyone between 5 feet and 6 feet tall."
New Way (Vector Intervals): You say, "Everyone who is taller than Person A AND shorter than Person B."

In this paper, a "Vector" is just a list of numbers representing a state (e.g., how many tokens are in different places of a network).

The Lower Bound (The "Must-Have"): A set of vectors that must be included. (e.g., "You must have at least 2 tokens here and 1 token there").
The Upper Bound (The "Must-Not-Have"): A set of vectors that must be excluded. (e.g., "You cannot have 10 tokens here").

This creates a "box" of valid states. Instead of listing every single valid state inside the box, the computer just remembers the boundaries.

The Magic Trick: Doing Math Without Opening the Box

The real genius of this paper isn't just describing the box; it's doing math on the box without ever opening it to count the items inside.

The Analogy: Imagine you have a box of apples. Usually, to add 5 more apples, you have to open the box, count them, add 5, and close it.
The Paper's Method: The authors created special rules (called Homomorphic Operations) that let you say, "Add 5 to the entire box," and the computer instantly updates the "Lower Bound" and "Upper Bound" labels. It never actually counts the apples. It just shifts the boundaries. This keeps the calculation incredibly fast, even if the box contains a billion apples.

Handling the "Messy" Parts: Canonical Forms

Sometimes, two different descriptions might actually mean the same thing.

Example: "Taller than 5ft, shorter than 10ft" is the same as "Taller than 5ft, shorter than 10ft."
But in complex math, you might get "Taller than 5ft, shorter than 10ft" and "Taller than 5ft, shorter than 9ft, but taller than 8ft." These are messy and redundant.

The authors created a Canonical Form. Think of this as a "Standardized ID Card."

No matter how you describe the group, the computer forces it into one specific, unique format.
This prevents the computer from wasting time doing the same calculation twice or storing the same group of people in two different ways.

The "Saturation" Trick: Skipping Steps

When the computer tries to find all possible states, it sometimes gets stuck in a loop, checking the same things over and over (like walking in circles in a maze).

The Solution: They use a technique called Saturation.
The Analogy: Imagine you are filling a bucket with water. Instead of checking every drop to see if the bucket is full, you just keep pouring until the water level stops rising. Once the level stabilizes, you know you're done.
In the paper, this allows the computer to jump ahead. If increasing the "capacity" (how many tokens a place can hold) doesn't change the result, the computer skips the middle steps and jumps straight to the answer.

The Results: Beating the Competition

The authors tested their tool (called SVSKit) on a famous competition (MCC 2022) involving complex "Petri Nets" (a type of diagram used to model systems like traffic lights or biological processes).

The Challenge: One specific test (the "Circadian Clock") had a capacity of 100,000. This is a huge number.
The Competition: Other top tools took over an hour and failed to solve all the questions.
The Result: The authors' tool solved all the questions in about 30 minutes.
Why? Because instead of counting every single possibility (which would take forever), they manipulated the "boxes" (the intervals) directly.

Summary

The paper introduces a new way to check if complex systems are safe. Instead of listing every single possible scenario (which is impossible for big systems), they use "Vector Intervals"—smart boxes defined by minimum and maximum limits. They invented math rules to manipulate these boxes without opening them and a "standardization" system to keep things tidy. This allows them to solve problems that other tools find too big to handle.

Technical Summary: Symbolic Model Checking using Intervals of Vectors

1. Problem Statement

Model checking is a robust formal verification technique for ensuring software and hardware systems adhere to specifications. However, it is severely hindered by the state space explosion problem, where the number of possible states and transitions grows exponentially with system size. This challenge is particularly acute in global model checking, where the objective is to identify all states satisfying a Computation Tree Logic (CTL) formula, rather than verifying a single configuration.

Existing techniques, such as Decision Diagrams (DDs), abstractions, and partial order reduction, mitigate this issue but face limitations as models become more sophisticated. Specifically, standard interval-based approaches (e.g., Interval Decision Diagrams) encode sets of vectors as vectors of intervals. This paper argues that a more effective approach for Petri nets is to encode sets of markings using generalized intervals on vectors (intervals of vectors), rather than vectors of intervals. This distinction is crucial because vector spaces often involve non-total partial orders, making simple interval definitions insufficient.

2. Methodology

The authors propose a novel symbolic structure called Symbolic Vector Sets (SVS) to encode sets of Petri net markings. The methodology is built upon three core pillars:

2.1. Symbolic Vectors and Sets

A Symbolic Vector is defined as a pair $(a, b)$ , where $a$ and $b$ are sets of vectors (markings).

Inclusion ( $a$ ): A marking $q$ belongs to the symbolic vector if it includes all vectors in $a$ (under a non-strict partial order $\subseteq_f$ ).
Exclusion ( $b$ ): A marking $q$ belongs to the symbolic vector if it does not include any vector in $b$ .
Generalization: This generalizes the natural number interval $[a, b]$ (where $a \le x \le b$ ) to vectors. Since vectors are not always comparable, the structure requires a set of lower bounds ( $a$ ) and a set of upper bounds ( $b$ ) rather than single bounds.

A Symbolic Vector Set is a collection of these symbolic vectors, representing the union of their underlying sets of markings.

2.2. Canonical Form and Operations

To ensure efficiency and avoid redundancy, the authors define a canonical form for symbolic vectors and sets. Key properties include:

Uniqueness: Every set of markings has exactly one canonical representation.
Homomorphic Operations: The paper defines homomorphic operations (union, intersection, difference, negation) that operate directly on the symbolic structures without decoding them to individual markings.
Mergeability and Shareability: To maintain canonicity, the authors introduce relations to determine when two symbolic vectors can be merged or when a "shareable" component exists between them. This involves a lexicographic total order to resolve ambiguities in non-total partial orders, ensuring deterministic handling of overlapping constraints.

2.3. CTL Model Checking on Petri Nets

The framework applies these structures to Petri nets with finite capacities.

Pre-Operation: The core of global model checking is the pre operation, which computes predecessor markings. The authors define a symbolic pre operation that works on symbolic vector sets, handling transition reversibility and capacity constraints.
Fixpoint Evaluation: CTL formulas (e.g., $EF$, $EG$, $EU$) are evaluated using fixpoint computations (least and greatest fixpoints) over the symbolic vector sets. The satisfaction of a formula is determined by checking if a marking belongs to the resulting symbolic vector set.

2.4. Optimizations

Saturation: To address the "peak effect" where intermediate solutions in fixpoint computations grow unnecessarily large, the authors implement a saturation strategy. This involves iterating on capacity bounds and leveraging previous results to compute subsequent steps, significantly reducing the number of intermediate symbolic vectors.
Clustering: The paper mentions clustering as a potential optimization for reachability, where smaller vectors are combined, though this is noted as a concept for future formal description.

3. Key Contributions

Novel Encoding: Introduction of Symbolic Vector Sets, a structure that generalizes intervals to vectors, specifically designed to handle the non-total partial order of Petri net markings.
Formal Canonicalization: A rigorous definition of a canonical form for symbolic vectors and sets, including proofs of uniqueness and the development of homomorphic operations (union, intersection, difference, negation) that preserve this canonicity.
Global Model Checking Framework: A complete formalism for evaluating CTL formulas on Petri nets using these symbolic structures, including the definition of the symbolic pre operation.
Saturation Algorithm: An adaptation of saturation principles (derived from other symbolic techniques) to the context of symbolic vector sets to mitigate computational peaks during fixpoint iterations.
Implementation (SVSKit): A Swift library implementing the theory, tested against benchmarks from the Model Checking Contest (MCC) 2022.

4. Results

The authors evaluated their approach using the SVSKit tool on examples from the MCC 2022, specifically the Circadian Clock model.

Scalability with Saturation: Experiments on the Circadian Clock model (14 places, 16 transitions) demonstrated that saturation is critical. Without saturation, computation time grew exponentially with place capacity (exceeding 5 hours for capacity 6). With saturation, time remained constant (approx. 3.2s) for capacities 2 and above, and the number of symbolic vectors remained stable.
Handling Large State Spaces: The tool successfully handled capacities up to $N=100,000$ , encoding approximately $10^{84}$ markings with a final set of only 26 symbolic vectors.
Benchmark Performance: In the CTL fireability category of MCC 2022, existing tools (GreatSPN, ITS-Tools, Tapaal) failed to answer all 16 queries within the 60-minute limit (Tapaal answered 9/16). The SVSKit approach solved all 16 queries in approximately 30 minutes.
Limitations: The authors acknowledge that the current implementation faces scalability challenges due to the worst-case complexity of canonical operations ( $O(n!)$ ). The efficiency relies heavily on the implementation of these operations, and the tool was restricted to relatively small Petri nets in the benchmarks due to these constraints.

5. Significance and Claims

The paper claims to offer a promising alternative to existing symbolic model checking techniques by shifting from "vectors of intervals" to "intervals of vectors."

Theoretical Contribution: It provides a formal algebraic framework for manipulating sets of vectors under partial orders, filling a gap in the literature where such structures were previously stagnant (referencing the original "Predicate structures" from 30 years prior).
Practical Viability: The results suggest that this approach can handle infinite or very large state spaces more efficiently than explicit enumeration and potentially outperform current tools on specific global model checking tasks, particularly those involving large capacities.
Future Directions: The authors modestly suggest that the current implementation requires refinement, particularly in optimizing canonical operations. They propose future work in local model checking, extending the approach to models beyond Petri nets, and integrating this method with Decision Diagrams, positing that the two approaches are orthogonal and could benefit from hybridization.

The paper concludes that while the current implementation has limitations, the theoretical foundation and initial experimental results validate the potential of symbolic vector sets for global model checking.