💻 computer science

A Forward-Only Construction of Semilinear Inductive Invariants for VAS

This paper introduces a novel forward-only construction of semilinear inductive invariants for Vector Addition Systems that derives invariants solely from the source configuration, thereby producing more canonical results aligned with system structure and offering a pathway to extend these techniques to asymmetric models like Branching VAS.

Original authors: Clotilde Bizière, Jérôme Leroux, Grégoire Sutre

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Clotilde Bizière, Jérôme Leroux, Grégoire Sutre

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 Picture: The "Can I Get There?" Problem

Imagine you have a robot in a giant warehouse (this is the Vector Addition System, or VAS). The robot starts at a specific spot (the Source) and has a list of moves it can make, like "move 2 steps forward," "move 1 step left," or "move 3 steps up."

The big question computer scientists ask is: Can the robot reach a specific target spot (the Target) without ever crashing into a wall (going into negative numbers)?

For decades, we knew the answer to this question could be found (it's "decidable"), but the methods to find the answer were complicated. One famous method, developed by Jérôme Leroux in the 2010s, was like a game of "tug-of-war."

The Old Way: The Tug-of-War (Back-and-Forth)

Leroux's original method tried to solve the problem by looking at the problem from both ends at the same time:

Forward: It imagined everything the robot could reach starting from the Source.
Backward: It imagined everything that could reach the Target if we ran the robot's moves in reverse.

The method kept expanding these two lists until they met in the middle or proved they could never touch. If they could never touch, it meant the Target was unreachable.

The Problem with this approach:

It's messy: The "proof" (called an inductive invariant) it creates depends heavily on both the starting point and the specific target you are checking. If you change the target even slightly, the whole proof changes.
It's not structural: Because it relies on the target, the proof doesn't really tell you much about the nature of the robot's warehouse itself. It's like trying to describe the shape of a room by looking at where a specific piece of furniture is, rather than looking at the walls.
It fails on complex systems: The authors point out that this "tug-of-war" method breaks down for more complex systems called Branching VAS (where the robot can split into two robots and merge them later). In those systems, you can't easily run things backward because the "history" gets tangled like a tree, not a straight line.

The New Way: The One-Way Street (Forward-Only)

The authors of this paper propose a new, cleaner way to solve the problem. Instead of looking backward from the target, they only look forward from the source.

The Analogy: Building a Fence
Imagine you want to prove the robot cannot reach a forbidden zone (the Target).

The Old Way: You tried to build a fence from the start, and someone else tried to build a fence from the forbidden zone, and you met in the middle to see if the fences touched.
The New Way: You start at the Source and build a fence that encloses everything the robot can possibly reach. You keep expanding this fence until it is a perfect, solid wall.
- If your fence naturally stops before it hits the forbidden zone, you have your proof.
- Crucially, this fence is built only based on the rules of the warehouse and the starting point. It doesn't care where the forbidden zone is.

Why This Matters: The "Periodic" Discovery

The paper makes a specific discovery about a special type of warehouse called a Periodic VAS.

What is it? Imagine a warehouse where the robot's moves are perfectly symmetrical. If the robot can go from Point A to Point B, it can also go from Point B to Point C, and the pattern repeats forever (like a clock or a calendar).
The Old Flaw: When the old "tug-of-war" method tried to build a fence for these periodic warehouses, the fence often looked jagged and irregular. It would include a spot, but miss the spot exactly "one cycle" away, breaking the beautiful repeating pattern of the warehouse.
The New Win: The authors' new "forward-only" method builds a fence that respects the pattern. If the warehouse is periodic, the fence (the invariant) is also periodic. It looks like a perfect, repeating grid.

The Main Takeaways

Simpler Logic: You don't need to look backward from the target to prove something is unreachable. You can just look forward from the start.
Better Proofs: The proofs generated by this new method are "canonical," meaning they are unique to the system itself, not dependent on which specific target you are testing. They reflect the true structure of the system.
Preserving Patterns: For systems that repeat themselves (periodic), the new method guarantees the proof will also repeat itself, which the old method often failed to do.
Future Potential: Because this method doesn't rely on "running backward" (which is impossible in branching systems), it opens the door to solving reachability problems for Branching VAS (systems where processes split and merge), which is currently a major unsolved mystery in computer science.

In a Nutshell

The authors replaced a complicated, two-sided guessing game with a streamlined, one-sided construction. They built a tool that creates "fences" around what a system can do, ensuring these fences are perfectly shaped to match the system's own internal logic, making it easier to prove what is impossible to reach.

Technical Summary: A Forward-Only Construction of Semilinear Inductive Invariants for VAS

Problem Statement
The reachability problem for Vector Addition Systems (VAS), also known as Petri nets, is a central decision problem in the theory of infinite-state systems. While decidability was established in the 1980s by Kosaraju and Mayr, the computational complexity remained open for decades until recently shown to be Ackermann-complete. A significant alternative approach to decidability, introduced by Leroux, characterizes non-reachability via semilinear inductive invariants. This method relies on a "back-and-forth" scheme that simultaneously expands a forward over-approximation from the source and a backward over-approximation from the target.

However, this existing approach has two primary limitations:

Symmetry Dependence: The construction relies on the symmetry of VAS, where runs can be reversed. This symmetry breaks down in asymmetric models like Branching VAS (BVAS), where executions are tree-shaped rather than linear sequences, making the extension of Leroux's method to BVAS difficult.
Lack of Canonicity: The resulting invariants depend equally on the source and the target. In many verification scenarios, the source is fixed while the target varies; a method producing invariants that change drastically with the target is less canonical and harder to relate to the system's intrinsic structure. Furthermore, for specific subclasses like periodic VAS, Leroux's method does not guarantee that the resulting invariants are periodic.

Methodology
The authors propose a new forward-only construction of semilinear inductive invariants. Unlike the back-and-forth approach, this method builds invariants solely from the set of initial configurations ( $C_0$ ) without requiring backward reasoning from the target.

The core technical ingredients include:

Periodic VAS: The authors define a class of VAS where the reachability set is periodic (closed under addition and containing the zero vector). They prove that the reachability problem for general VAS can be reduced to the reachability problem for periodic VAS by adding a single counter.
Almost Semilinear Sets and Linearization: The method utilizes the geometric characterization of VAS reachability sets as "almost semilinear" sets. These are decomposed into "almost linear" sets ( $b + P$ ), which are then over-approximated by linear sets via a process called linearization ($lin(L)$).
Interior Vectors: A novel concept introduced in this work is that of "interior vectors" of a periodic set. These vectors allow the algorithm to refine approximations by pushing vectors into the original set, ensuring that the constructed invariant remains disjoint from the target set while maintaining periodicity.
Algorithmic Construction: The paper presents an algorithm (Algorithm 1) that iteratively refines a semilinear periodic set $Inv$. In each iteration, it identifies the difference between the forward reachability of the current set and the set itself, decomposes this difference into almost linear components, and adds specific translated linearizations to $Inv$. The algorithm is proven to terminate because the "space-dimension" of the difference set strictly decreases with each iteration.

Key Contributions

Forward-Only Construction: The authors introduce a method to construct semilinear inductive invariants that depends primarily on the reachable configurations from the source. This yields invariants that are more canonical and better aligned with the system's structure.
Periodic Invariants for Periodic VAS: The paper proves that for periodic VAS, if the reachability set is disjoint from a semilinear target set, there exists a periodic semilinear inductive invariant that is also disjoint from the target. This contrasts with previous methods which could produce non-periodic invariants even for periodic systems.
Reduction to Periodic VAS: The authors provide an effective characterization of periodic VAS and demonstrate that the reachability problem for plain VAS reduces to that of periodic VAS. Consequently, semilinear invariants for general VAS can be derived from the periodic invariants constructed for the reduced system.
Existence Proof via Oracle: The construction is presented as an algorithm with oracle calls (for linearization and vector selection). The paper establishes the existence of the necessary vectors and the termination of the process, providing a constructive proof of the existence of periodic semilinear inductive invariants.

Results

Theorem 4.5: The reachability set of a periodic VAS $(A, C_0)$ has an empty intersection with a semilinear set $C_{bad}$ if and only if there exists a periodic semilinear inductive invariant $I$ of $(A, C_0)$ such that $I \cap C_{bad}$ is empty.
Termination and Correctness: The proposed algorithm terminates and returns a semilinear periodic inductive invariant disjoint from the target set, provided the oracle calls can be satisfied. The termination is guaranteed by the strict decrease in the space-dimension of the set $Post^*_A(Inv) \setminus Inv$ at each step.
Examples: The paper illustrates the method with examples where the forward-only construction produces invariants that are independent of the specific target configuration (unlike the back-and-forth method) and, in the case of periodic VAS, produces periodic invariants where the back-and-forth method fails to do so.

Significance and Claims
The authors claim that this forward-only approach represents a step toward extending invariant-based techniques to Branching VAS (BVAS). Since BVAS lack the symmetry required for backward reasoning (initial configurations are at the leaves, targets at the root of execution trees), the symmetry-dependent back-and-forth method is difficult to generalize. By constructing invariants purely from the source, the authors suggest their method is more suitable for addressing the open reachability problem for BVAS.

The paper also discusses the "semilinear inductive invariant" property in the context of Grammar VAS (GVAS), conjecturing that similar properties may hold, though this remains an open area for future investigation. The work is framed as a theoretical advancement in the structural understanding of VAS reachability, offering a more canonical tool for verification that respects the asymmetry of certain system models.