💻 computer science

Taking Complete Finite Prefixes To High Level, Symbolically

This paper unifies the concepts of unfoldings and complete finite prefixes to define and construct complete finite prefixes for the symbolic unfoldings of high-level Petri nets, generalizing existing algorithms for safe nets and extending the methodology to handle nets with infinitely many reachable markings through an adapted cut-off criterion.

Original authors: Nick Würdemann, Thomas Chatain, Stefan Haar, Lukas Panneke

Published 2026-04-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nick Würdemann, Thomas Chatain, Stefan Haar, Lukas Panneke

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

Imagine you are trying to solve a massive, complex puzzle, like a giant maze or a game of chess, but the rules allow for millions of different variations of the pieces. You want to know: "Can I reach the finish line?" and "What are all the possible ways to get there?"

In the world of computer science, these puzzles are called Petri Nets. They are used to model everything from traffic lights to computer processors.

The Problem: The "Low-Level" Explosion

Traditionally, to solve these puzzles, computers had to break everything down into tiny, individual pieces. Imagine a game where you have a bucket of 1,000 different colored marbles.

The Old Way (Low-Level): The computer treats every single marble as a unique, separate object. If you have 1,000 colors, the computer has to build a map for every single combination of those 1,000 colors. The map becomes so huge (like a library with billions of books) that the computer runs out of memory and crashes before it can find the answer.

The Solution: The "High-Level" Shortcut

The authors of this paper, Nick Würdemann and his team, developed a smarter way to look at the puzzle. Instead of looking at individual marbles, they look at the rules and patterns.

The New Way (High-Level/Symbolic): Instead of saying "Red Marble A, Blue Marble B," the computer says, "Any marble that is not Red." It uses symbols (like variables in math: $x$ , $y$ ) to represent whole groups of possibilities at once.

Think of it like this:

Low-Level: You have to write a separate instruction manual for every single person in a stadium.
High-Level: You write one instruction manual that says, "If you are wearing a red shirt, do X. If you are wearing a blue shirt, do Y." This manual is tiny, but it covers everyone.

The "Complete Finite Prefix": The Perfect Cheat Sheet

The goal of the paper is to create a "Complete Finite Prefix."
Imagine you are exploring a cave. You want to know if there's a treasure at the end.

The Cave: The Petri Net (the system).
The Path: The Unfolding (all possible paths you can take).
The Problem: The cave is infinite. You can't walk every path.
The Cheat Sheet: The authors created a method to build a finite map (a prefix) that is small enough to fit in your pocket but still guarantees that if the treasure exists, it will be on this map. If the map says "No treasure," then there is definitely no treasure.

They took a famous algorithm (the ERV algorithm) that was good for simple puzzles and upgraded it to handle these complex, high-level puzzles with symbols.

The "Cut-Off" Trick: When to Stop

How do they keep the map small? They use a "Cut-Off" rule.
Imagine you are walking through the cave. You reach a fork in the road. You realize, "Wait, I've been in a room that looks exactly like this one before, and I already explored everything that could happen from there."

The Cut-Off: You stop exploring this new path because you know it won't give you any new information. You mark it as "Done."
The Innovation: In the old way, you could only stop if you saw the exact same room. In this new symbolic way, you can stop if you see a room that is symbolically equivalent.
- Example: If you visited a room with "3 red marbles" and now you are in a room with "3 blue marbles," the old computer says "Keep going, it's different!" The new computer says, "Stop, the pattern is the same; the result will be the same."

Handling the "Infinite"

Some puzzles are so complex that they have an infinite number of possible states (like counting forever). The old algorithms would get stuck in an infinite loop.
The authors identified a special class of these infinite puzzles called "Symbolically Compact."

The Metaphor: Imagine a machine that can produce infinite numbers, but it only takes 5 steps to produce any number you want. Even though the list of numbers is infinite, the process to get there is short.
The authors tweaked their "Cut-Off" rule to handle these. They realized that even if the list of outcomes is infinite, if you can reach them all quickly, you can still build a finite map to prove they exist.

The "Mode-Determinism" Test

The team also discovered a "secret indicator" to predict which method is faster. They call it Mode-Determinism.

High Determinism (Predictable): If the rules are so strict that there is only one way to move a piece in any given situation, the old "Low-Level" method is actually quite fast. The symbolic shortcut doesn't help much because there are no "groups" to compress.
Low Determinism (Chaotic): If a piece can move in 1,000 different ways depending on the situation, the "High-Level" symbolic method is a massive winner. It collapses those 1,000 possibilities into one symbol.

The Results

They tested their new tool (called COLORUNFOLDER) on four types of puzzles:

Fork and Join: Splitting a task into many parts. (Symbolic was thousands of times faster).
Water Pouring Puzzle: The classic "measure 4 liters with a 3L and 5L jug" riddle. (Low-level was faster here because the rules were very strict/predictable).
Hobbits and Orcs: A river-crossing logic puzzle. (Symbolic won when the boat got bigger and more chaotic).
Mastermind: The code-breaking game. (Symbolic crushed the competition, solving huge versions in seconds that the old method couldn't finish in minutes).

The Bottom Line

This paper is like upgrading from a magnifying glass to a telescope.

Before: We could only look at small, simple systems or systems with very few variations.
Now: We have a tool that can look at complex systems with infinite variations, compress them into a manageable size, and tell us definitively if a solution exists, without getting lost in the details.

It's a huge step forward for verifying that complex software, hardware, and safety-critical systems (like airplane controllers or nuclear plant monitors) will behave correctly, even when they have millions of possible states.

1. Problem Statement

Petri nets are a standard formalism for modeling distributed systems. Place/Transition (P/T) nets (low-level) have a well-established theory of unfoldings, which represent the partial-order semantics of a net. A complete finite prefix of an unfolding contains all necessary information to verify properties like reachability without exploring the entire (potentially infinite) state space. The Esparza, Römer, and Vogler (ERV) algorithm is the standard method for constructing these small, complete prefixes for safe P/T nets.

High-level Petri nets (e.g., Colored Petri nets) offer a more concise representation by allowing places to hold tokens of different "colors" (values) and transitions to have guards (logical constraints). While symbolic unfoldings exist for high-level nets, a major challenge remains:

Existing algorithms for constructing complete finite prefixes generally fail for high-level nets with infinitely many reachable markings.
Simply expanding a high-level net into a low-level P/T net (the "expansion") and applying the ERV algorithm is often computationally infeasible because the expansion can be exponentially larger or even infinite.
The paper addresses the gap in constructing complete finite prefixes directly at the symbolic (high-level) level, preserving the compactness of the high-level representation while ensuring termination and completeness.

2. Methodology

The authors propose a generalization of the ERV-algorithm to the symbolic level, introducing new theoretical constructs to handle the complexity of high-level nets.

A. The Class $NF$ (Finite Reachability)

The authors first define a class of safe high-level Petri nets ($NF$) satisfying three conditions:

Safety: Every place holds at most one token in any reachable marking.
Decidable Guards: Guards are expressed in a decidable logic (e.g., Presburger arithmetic).
Finite Reachability: The net has a finite number of reachable markings.

For this class, they generalize the concepts of adequate orders and cut-off events from the low-level case to the symbolic level.

Symbolic Adequate Orders: They lift the partial order on configurations to symbolic configurations. Crucially, they define a monomorphism between the futures of configurations that represent overlapping sets of markings, rather than requiring identical markings (which would be too restrictive).
Symbolic Cut-off Events: In the low-level case, an event is a cut-off if its marking has been seen before. In the symbolic case, an event $e$ is a cut-off if the set of markings reachable via its cone configuration, $M([e])$ , is a subset of the union of markings reachable via all preceding configurations. This allows the algorithm to prune branches even if the exact marking hasn't been seen, provided all possible markings in that branch have been covered by previous branches.

B. The Class $NSC$ (Symbolically Compact Nets)

To handle nets with infinitely many reachable markings (where the expansion is infinite), the authors introduce the class $NSC$ (Symbolically Compact Nets).

Definition: A net is symbolically compact if there exists a bound $n$ on the number of transition firings required to reach any reachable marking, even if the total number of markings is infinite.
Adapted Algorithm: The standard cut-off criterion fails for $NSC$ because the "pigeonhole principle" (relying on finite state space size) no longer applies. The authors introduce a cut-off criterion: an event is a cut-off if its reachable markings are covered by any preceding configuration (not just cone configurations) in the prefix.
Symbolic Checking: To verify the cut-off* criterion without enumerating infinite sets, they define constraints (predicates) that symbolically describe the set of markings represented by a configuration's cut. Checking if an event is a cut-off reduces to checking the logical implication of these constraints using an SMT solver.

C. Implementation

The authors implemented a prototype tool called COLORUNFOLDER in Java.

It uses the CVC5 SMT solver to handle the satisfiability checks of guards and the implication checks for cut-off criteria.
It employs optimizations such as variable renaming to reduce the number of variables in predicates, significantly speeding up SMT queries.

3. Key Contributions

Theoretical Generalization: The paper successfully unifies the concepts of complete finite prefixes and symbolic unfoldings. It proves that for safe high-level nets, the generalized ERV-algorithm produces a finite and complete prefix.
Handling Infinite Markings: It identifies the class of symbolically compact nets and provides a mechanism (the cut-off* criterion with symbolic constraint checking) to construct finite prefixes for nets with infinite state spaces, a scenario where traditional expansion-based methods fail.
Symbolic Cut-off Logic: The introduction of subset-based cut-off criteria and the method for symbolically verifying marking inclusion via logical implication is a novel contribution to concurrency theory.
Mode-Determinism: The authors identify a net property called mode-determinism (where every transition fires in at most one mode per reachable marking). They show that symbolic unfolding offers significant performance advantages over low-level unfolding primarily when nets are mode-nondeterministic.

4. Experimental Results

The authors evaluated the prototype on four benchmark families:

Fork And Join: A highly mode-nondeterministic net. The symbolic approach was orders of magnitude faster than the low-level approach, with execution time independent of the color domain size (even for infinite domains).
Water Pouring Puzzle: A mode-deterministic net. Here, the symbolic and low-level approaches produced isomorphic structures. The low-level approach was often faster due to the overhead of SMT solving, confirming that symbolic benefits diminish for deterministic nets.
Hobbits And Orcs: A river-crossing puzzle. The symbolic approach outperformed the low-level approach as the boat capacity (and thus mode-nondeterminism) increased.
Mastermind: A code-breaking game. The symbolic approach consistently outperformed the low-level approach, especially as the number of colors and code length increased, demonstrating scalability where the low-level approach timed out.

Key Finding: The symbolic approach is superior for nets with high mode-nondeterminism and large or infinite color domains. For mode-deterministic nets, the low-level approach may be competitive or faster due to lower overhead.

5. Significance

This work bridges a critical gap in the verification of high-level concurrent systems.

Scalability: It enables the verification of systems with infinite state spaces (e.g., systems with unbounded integer variables) without resorting to state-space explosion caused by low-level expansion.
Efficiency: By operating directly on the high-level abstraction, it avoids the exponential blowup associated with expanding colored nets into P/T nets.
Foundational Impact: It extends the powerful theory of partial-order reduction (via unfoldings) to the high-level domain, providing a rigorous algorithmic framework for model checking complex, parameterized systems.
Future Directions: The paper lays the groundwork for symbolic reachability graphs and the application of these techniques to Petri games (synthesis of strategies), suggesting a path toward solving complex synthesis problems in high-level models.