💻 computer science

A rewriting-logic-with-SMT-based formal analysis and parameter synthesis framework for parametric time Petri nets

This paper introduces a sound and complete formal analysis and parameter synthesis framework for parametric time Petri nets with inhibitor arcs by defining a rewriting logic semantics compatible with Maude and SMT solving, which enables advanced verification capabilities and often outperforms existing tools like Romeo.

Original authors: Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

Published 2026-04-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

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 designing a complex traffic light system for a busy city intersection. You know the rules: cars can't run red lights, and pedestrians need enough time to cross. But you don't know the exact numbers yet. How long should the green light stay on? Is it 30 seconds? 45? What if the traffic volume changes?

This is the problem of Parametric Time Petri Nets (PITPNs). It's a way to model systems where time matters, but the exact timing values are unknown "parameters." You want to find the perfect settings (the parameters) that keep the system safe and efficient.

Currently, there's a specialized tool called Roméo that helps engineers solve these puzzles. But Roméo has limits: it can't handle every type of question, it struggles with complex "what-if" scenarios, and sometimes it just gives up or says "maybe."

This paper introduces a new, more powerful approach using a tool called Maude combined with a "super-smart calculator" called an SMT solver. Here is how they did it, explained simply:

1. The Two Languages: Concrete vs. Symbolic

The authors first built a "dictionary" to translate the traffic light system (PITPN) into the language of Maude.

The Concrete Version (The "Real" Simulation): Imagine you have a physical model of the traffic lights. You set the timer to exactly 30 seconds and watch what happens. This is the "concrete" view. The authors proved that their Maude translation behaves exactly like the real system.
- The Catch: You can't simulate every possible time (30.0001 seconds? 30.0000001?). If you try to check every single fraction of a second, the computer gets stuck in an infinite loop.
The Symbolic Version (The "Magic" View): Instead of setting the timer to 30, you set it to a variable, let's call it $X$ . The system doesn't just run; it thinks. It asks the SMT solver (the super-smart calculator): "For what values of $X$ does the system crash?" or "For what values of $X$ is the system safe?"
- This allows them to find the entire range of safe numbers at once, rather than testing one by one.

2. The "Folding" Trick (Avoiding the Infinite Loop)

Here is the biggest hurdle. Even with the "Magic View," the system can generate an infinite number of possibilities. Imagine a tree where every branch splits into more branches. If you keep exploring, you'll never finish.

The authors invented a new "Folding" technique.

The Analogy: Imagine you are exploring a maze. In the old way, if you walked down a path and saw a red door, you marked it. If you walked down a different path and saw a red door that looked slightly different (maybe the handle was turned a different way), you treated it as a new, unique door and kept walking.
The New Way: The "Folding" technique realizes that even if the handle is turned differently, the essence of the room is the same. It "folds" these similar-looking paths together. It says, "I've already seen a room like this; I don't need to walk down this new branch."
The Result: This prevents the computer from getting lost in an infinite maze. It guarantees that if a solution exists (or if the system is safe), the computer will find it and stop.

3. What Can This New Tool Do?

The authors showed that their Maude-based tool can do everything Roméo can do, plus much more:

The "What-If" Scenarios: You can ask, "What happens if I always force the left-turn light to go before the straight-ahead light?" Roméo makes you rebuild the whole model to test this. Maude lets you just write a simple rule and run the test instantly.
The "Starting Point" Mystery: Usually, you assume the system starts with empty places. Maude can figure out: "What if we started with 2 cars in the left lane instead of 0? What initial conditions make the system safe?"
Full Logic Checking: It can check complex, nested stories like, "Is it true that whenever a car enters, eventually it will leave, unless a pedestrian crosses?"
Speed: Surprisingly, this high-level "prototype" tool often runs faster than the highly optimized, industrial-grade Roméo tool, especially on difficult problems.

4. The "Maybe" Problem

Sometimes, Roméo looks at a problem and says, "I don't know, maybe it's safe, maybe it's not." This is frustrating for engineers.
The authors found that in cases where Roméo said "maybe," their Maude tool could often find the exact answer. When they took Maude's answer and fed it back into Roméo, Roméo confirmed, "Oh, you're right, it is safe!"

Summary

Think of this paper as upgrading from a manual calculator (Roméo) to a super-intelligent AI assistant (Maude + SMT).

The AI doesn't just crunch numbers; it understands variables and logic.
It has a special "folding" trick to avoid getting overwhelmed by infinite possibilities.
It can answer deeper, more complex questions about how systems behave over time.
And best of all, it's built on a flexible framework that makes it easy for researchers to invent new ways to test these systems without starting from scratch.

The authors have essentially built a universal "testbed" for time-sensitive systems, proving that a flexible, high-level approach can sometimes outperform specialized, rigid tools.

1. Problem Statement

Parametric Time Petri Nets with Inhibitor Arcs (PITPNs) are a powerful formalism for modeling real-time systems where transition firing intervals are defined by unknown parameters rather than concrete constants. While the state-of-the-art tool Roméo supports analysis and parameter synthesis for PITPNs, it has significant limitations:

Limited Property Support: It cannot handle full (nested) temporal logic properties (e.g., full LTL) or complex user-defined execution strategies.
Initial Marking Constraints: It cannot synthesize parameters for parametric initial markings (where the initial number of tokens is unknown).
Lack of a Testbed: As a high-performance C++ tool with dedicated algorithms, it is difficult to rapidly prototype new analysis methods or strategies.
Decidability Issues: Standard explicit-state analysis in dense-time systems (like Real-Time Maude) is often unsound or incomplete because it cannot cover all time points.

The paper addresses the need for a sound, complete, and flexible framework that supports a broader range of analyses, including parameter synthesis for both firing bounds and initial markings, full LTL model checking, and custom execution strategies.

2. Methodology

The authors propose a framework based on Rewriting Logic (implemented in Maude) combined with Satisfiability Modulo Theories (SMT) solving. The methodology proceeds in three main stages:

A. Concrete Semantics (Real-Time Maude Style)

The authors first define a "concrete" rewriting logic semantics for instantiated PITPNs.

Representation: Markings are represented as maps (place $\to$ token count) rather than multisets to facilitate symbolic analysis. Time is modeled using "clocks" (time elapsed since a transition became enabled) rather than decreasing intervals to avoid negative values and simplify the state space.
Bisimulation: They prove that this rewriting logic semantics is bisimilar to the standard semantics of PITPNs.
Limitation: This concrete model is non-executable in dense time because the "tick" rule introduces a variable for time advancement ( $T$ ) that cannot be instantiated concretely without sampling.

B. Symbolic Semantics (Maude-with-SMT)

To handle parameters and dense time, the authors develop a symbolic rewriting logic semantics ( $R^S_1$ ).

Symbolic States: States are represented as constrained terms $\phi \parallel t$ , where $t$ is a state pattern containing variables (parameters, clock values, token counts) and $\phi$ is an SMT constraint restricting these variables.
Execution: Rules are applied symbolically. When a rule fires, new constraints are accumulated, and the SMT solver checks for satisfiability.
Soundness & Completeness: Theorem 5.2 proves that the symbolic semantics captures all behaviors of concrete PITPNs for any parameter valuation and vice versa.

C. The Folding Mechanism (Termination)

A critical challenge in symbolic reachability is that even if the state-class graph is finite, the symbolic state space can be infinite due to fresh variables generated at each time step (e.g., different tick variables representing the same logical state).

New Folding Relation ( $\preceq$ ): The authors propose a novel subsumption relation based on existential quantification. Instead of simple syntactic matching, they abstract the current state by replacing concrete clock/marking values with fresh variables and checking if the existential projection of one state implies another.
Implementation: Two implementations are provided:
1. Branch-local folding: Uses Maude's standard search command but only folds states within the same search branch.
2. Global folding (Meta-level): Uses Maude's meta-programming facilities to implement a Breadth-First Search (BFS) that maintains a global set of visited states across all branches, ensuring termination whenever the state-class graph is finite.
Optimization: The framework integrates the Fourier-Motzkin Elimination (FME) procedure as an equational theory within Maude. This allows the elimination of existentially quantified variables without relying on specific SMT solver features (like Z3's specific quantifier elimination), making the tool solver-agnostic.

3. Key Contributions

Unified Framework: A single Maude-based framework that supports both concrete (explicit-state) and symbolic (SMT-based) analysis of PITPNs.
Extended Analysis Capabilities:
- Parameter Synthesis: Supports synthesis for both transition firing bounds and parametric initial markings.
- Full LTL Model Checking: Supports nested temporal logic formulas, which Roméo does not.
- User-Defined Strategies: Allows analysis under specific execution strategies (e.g., "always fire transition $t$ before $t'$ if both are enabled").
- Transition Clock Properties: Can synthesize parameters based on constraints involving the values of transition clocks, not just markings.
Novel Folding Algorithm: A sound and complete folding method for symbolic reachability that guarantees termination for finite state-class graphs, overcoming the limitations of standard subsumption in rewriting modulo SMT.
Solver Agnosticism: By implementing FME internally, the framework works with any SMT solver connected to Maude (Yices2, CVC4, Z3).

4. Results and Benchmarking

The authors benchmarked their framework against Roméo (v3.9.4) and their previous implementation (from a conference paper) using six PITPN case studies (producer-consumer, scheduling, tutorial, and train systems).

Performance:
- In many cases, the Maude-based prototype outperformed Roméo in execution time.
- Termination: Maude successfully solved instances where Roméo timed out or returned "maybe" (an approximation). In some cases, Maude found solutions that Roméo missed; these solutions were later validated by re-running Roméo with the synthesized constraints.
- Solver Impact: Maude connected with Yices2 was generally the fastest. The new implementation using internal FME was significantly faster than the previous version relying on Z3's quantifier elimination.
Functionality:
- The framework successfully performed safety synthesis (AG-synthesis) and reachability synthesis (EF-synthesis) for parametric initial markings, a feature unsupported by Roméo.
- Full LTL model checking was demonstrated on complex nested formulas.

5. Significance

This work represents a significant step forward in the formal analysis of dense-time real-time systems.

Flexibility: It transforms Maude from a general-purpose specification language into a powerful, flexible backend for PITPN analysis, acting as a "testbed" for developing new algorithms.
Completeness: It bridges the gap between the expressiveness of rewriting logic and the decidability requirements of real-time systems by providing a sound and complete symbolic analysis method.
Extensibility: The use of meta-programming makes it easy to prototype new analysis methods (e.g., new strategies or temporal logics) without rewriting the core engine.
Future Impact: The authors note that this approach paves the way for extending "symbolic Real-Time Maude" to even more complex classes of real-time systems beyond PITPNs.

In summary, the paper demonstrates that a high-level, rewriting-logic-based approach combined with SMT solving can not only match but often exceed the performance of specialized, low-level tools like Roméo, while offering a much broader and more flexible set of analysis capabilities.