💻 computer science

Dense Integer-Complete Synthesis for Bounded Parametric Timed Automata

This paper introduces a parametric extrapolation method and associated algorithms that guarantee termination for synthesizing dense, integer-complete sets of parameter valuations ensuring reachability, unavoidability, and untimed behavior preservation in bounded parametric timed automata, despite the general undecidability of the problem.

Original authors: Étienne André, Didier Lime, Olivier H. Roux

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Étienne André, Didier Lime, Olivier H. Roux

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 an engineer designing a complex traffic light system or a robotic assembly line. These systems have two critical features: they do things in a specific order (concurrency), and they must do them at exact times (timing).

To make sure these systems don't crash or cause accidents, we use a mathematical tool called a Timed Automaton. Think of this as a flowchart where every step has a clock ticking next to it. For example, "Wait for 5 seconds, then open the gate."

The Problem: The "Unknown" Variables

Often, when designing these systems, we don't know the exact numbers yet. Maybe we know the gate must stay open for some amount of time, but we haven't decided if it's 5 seconds, 5.5 seconds, or 5.23 seconds. In math terms, these unknown numbers are called parameters.

When we add these unknowns to our flowchart, it becomes a Parametric Timed Automaton (PTA). The big question is: "What values can we give to these unknowns so that the system works perfectly?"

This is called Synthesis. We want to find a list of "good" numbers.

The Old Way: The Integer Trap

Previously, computer scientists had a method to solve this, but it had a major flaw. It could only find whole numbers (integers).

The Analogy: Imagine you are trying to find the perfect temperature for a cake. The old method could only tell you, "350 degrees works, 351 works, 352 works." It couldn't tell you that 350.5 also works, or that 350.1 is the perfect sweet spot.
The Danger: In real life, things aren't always whole numbers. If your system relies on a timing of 350.1 seconds, and your computer only checks 350 and 351, you might miss the solution entirely or think the system is broken when it's actually fine.

Furthermore, for complex systems, the old methods often got stuck in an infinite loop, never giving an answer at all.

The New Solution: "Dense Integer-Complete" Synthesis

The authors of this paper invented a new set of algorithms (named RIEF, RIAF, and RITP) that solve this problem in three clever ways:

It Finds the "Whole" Picture (Density):
Instead of just listing whole numbers, the new method finds a continuous range of numbers.
- The Analogy: Instead of giving you a list of specific rungs on a ladder (1, 2, 3), it gives you the entire ladder, including the spaces between the rungs. It guarantees that if a whole number works, the method finds it. But it also finds all the "in-between" numbers (like 3.5 or 3.99) that also work. This is crucial for robustness—ensuring the system works even if the timing is slightly off due to manufacturing errors.
It Always Stops (Termination):
The old methods would sometimes run forever, like a hamster on a wheel. The new method uses a special mathematical trick called Parametric Extrapolation.
- The Analogy: Imagine you are exploring a maze. The old method would keep walking down a hallway that gets longer and longer, never realizing it's going in circles. The new method puts up a "Stop Sign" based on the maximum size of the maze. If you've seen a section of the maze that looks "big enough" (mathematically similar to a previous section), it says, "Okay, we've seen this pattern; we don't need to walk further." This guarantees the computer finishes its job and gives you an answer.
It Handles Three Types of Safety Checks:
The paper provides tools for three different safety questions:
- Reachability (RIEF): "Can we ever reach the finish line?" (e.g., Can the robot ever pick up the part?)
- Unavoidability (RIAF): "Is it impossible to get stuck?" (e.g., Will the robot always eventually pick up the part, no matter what delays happen?)
- Trace Preservation (RITP): "If we change the numbers slightly, does the system still do the exact same dance?" (e.g., If we tweak the timing, does the robot still move in the same sequence of steps?)

How They Tested It

The authors didn't just write theory; they built these tools into software called Roméo and IMITATOR. They tested them on classic problems:

Scheduling: Making sure three different tasks get done without fighting over resources.
Fischer's Protocol: A classic test for ensuring multiple computers don't try to use a shared resource at the exact same time.
Level Crossing: Ensuring a train never hits a gate that is still opening.

In many cases, the old tools either gave up (ran forever) or said "No solution exists" because they only looked for whole numbers. The new tools found valid solutions, often revealing that a solution exists even when the numbers aren't perfect integers.

The Bottom Line

This paper gives engineers a way to mathematically prove that their time-sensitive systems will work, even when they haven't decided on the exact numbers yet. It guarantees that if a solution exists using whole numbers, the tool will find it, but it goes a step further to find the "in-between" numbers too, making the system safer and more reliable in the real world. And best of all, the computer will actually finish the calculation and give you an answer.

Technical Summary: Dense Integer-Complete Synthesis for Bounded Parametric Timed Automata

Problem Statement
The verification of real-time systems often relies on Parametric Timed Automata (PTAs), which extend standard timed automata by allowing timing constants to be parameters rather than fixed values. A central challenge in this domain is parameter synthesis: computing the set of parameter valuations that guarantee specific behavioral properties, such as reachability (EF), unavoidability (AF), or the preservation of untimed traces.

While the reachability-emptiness problem is undecidable for general PTAs, even with bounded parameters, existing synthesis algorithms face a trade-off between termination and result quality. Previous work, such as the IEF and IAF algorithms, guarantees termination for bounded parameters but only by synthesizing sets of integer parameter valuations. Interpreting these integer results as dense sets (containing rational values) is often incorrect, as non-integer valuations within the synthesized constraints may fail to satisfy the desired property. Conversely, algorithms that attempt to synthesize dense sets (like the standard EF algorithm) generally do not terminate for bounded PTAs because the number of symbolic states can be infinite when parameters are rational.

Methodology
The authors propose a novel approach to synthesize dense under-approximations of the solution set that are integer-complete. This means the output is a symbolic set (a finite union of polyhedra) that contains all correct integer parameter valuations and all convex combinations of these integers (rational points), while guaranteeing algorithm termination.

The core of the methodology involves three main components:

Parametric Extrapolation ( $Ext^M_X$ ):
The paper introduces a new extrapolation operator adapted for PTAs with bounded parameter domains. Unlike classical M-extrapolation for timed automata, which relies on a fixed maximum constant $M$ derived from integer guards, this operator computes $M$ based on the maximum possible value of parametric expressions over the bounded parameter domain.
- For a polyhedron $C$ and a clock $x$ , $Ext^M_x(C)$ is defined as the union of the part of $C$ where $x \le M$ and the cylindrification of the part where $x > M$ .
- Crucially, this operator preserves the projection onto the parameter space and ensures that for any integer parameter valuation, the extrapolated state is bisimilar to the original state.
Integer Hulls ($IH$):
The algorithms utilize the integer hull operator, which computes the convex hull of the integer points within a polyhedron. The key theoretical insight (Proposition 3.18) is that the set of integer hulls of the extrapolated symbolic states in a bounded PTA is finite. This finiteness allows the algorithms to terminate by detecting loops in the state space based on the equality of these integer hulls, rather than the states themselves.
Three Synthesis Algorithms:
The authors implement three recursive algorithms that explore the parametric symbolic state graph (without initial extrapolation) but use the integer hull of the extrapolated state for the termination check (the Passed set):
- RIEF (Robust Integer-Complete EF): Synthesizes parameter valuations ensuring a target location is reachable. It returns the actual symbolic states (dense) but uses integer hulls for convergence.
- RIAF (Robust Integer-Complete AF): Synthesizes valuations ensuring a target location is unavoidable. It handles deadlocks and loops by intersecting "good" branches with "blocking" branches, ensuring the result is dense and correct.
- RITP (Robust Integer-Complete Traces Preservation): Synthesizes valuations that preserve the trace set of a reference integer valuation. It modifies the "Inverse Method" (TP) by using integer hulls of extrapolated states for termination and requiring the reference valuation to be an integer to ensure soundness.

Key Contributions

Termination with Dense Results: The paper presents the first synthesis algorithms that terminate for bounded PTAs (where emptiness is undecidable) while outputting dense sets of valuations.
Integer-Completeness: The algorithms guarantee that the synthesized set contains all correct integer valuations. The result is an under-approximation that may miss some non-integer points but includes all integer solutions and their convex combinations.
Correction of Previous Misconceptions: The authors demonstrate that interpreting the results of previous integer-only algorithms (like IAF) as dense sets is incorrect. Their algorithms provide the correct dense constraints.
New Extrapolation Operator: The derivation of a maximum-constant-based parametric extrapolation operator that ensures termination for bounded PTAs with rational parameters.

Experimental Results
The authors implemented these algorithms in the tools Roméo (for RIEF and RIAF) and IMITATOR (for RITP), utilizing the Parma Polyhedra Library (PPL) for polyhedral operations. Experiments were conducted on several benchmarks:

Scheduling and Mutual Exclusion: In the Fischer mutual exclusion protocol, RIEF produced results comparable to the non-terminating EF algorithm but with guaranteed termination, while being more precise than the integer-only IEF. In cases where IEF produced an empty set (no integer solution), RIEF successfully found dense rational solutions (e.g., in the Level Crossing benchmark).
Trace Preservation: For the trace preservation problem, the standard TP algorithm often fails to terminate due to diverging constraints. RITP successfully terminated on these same examples, synthesizing the maximal dense set of valuations.
Performance: While RIEF and RIAF incur a computational overhead due to the calculation of integer hulls (typically a factor of 2–4x slower than their integer-only counterparts in specific cases), they remain efficient enough to solve problems that EF cannot (due to non-termination) and provide results that IEF cannot (due to lack of density).

Significance and Claims
The paper claims that these algorithms represent a significant advancement by bridging the gap between decidability and result precision. The authors emphasize that synthesizing dense sets is crucial for robustness and implementability, as real-world systems rarely operate on exact integers. By guaranteeing that the synthesized dense set contains all integer solutions, the method provides a "safe" under-approximation that designers can use with confidence.

The authors modestly note that while their approach is generic, it is currently limited to bounded parameter domains. They suggest future work could extend this to more complex abstractions (like LU-extrapolation) and more complex temporal logic properties (LTL/CTL). The work does not claim to solve the general undecidability of PTA emptiness but rather provides a practical, terminating method to derive dense, integer-complete under-approximations for bounded systems.