On the expressive power of invariants in parametric timed automata

Didier Lime; \'Etienne Andr\'e; Mathias Ramparison

REVIEW 2 major objections 3 minor 6 references

On the expressive power of invariants in parametric timed automata

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Removing guards from parametric timed automata leaves reachability decidable and yields exact parameter synthesis in exponential time.

desk verdict The paper's core reachability and synthesis theorems are false under its own syntax—negative offset constants break the zero-pattern lemmas—but the guard-to-invariant encoding is sound and the main results are likely repairable by restricting constants to nonnegative integers. read the letter →

arxiv 1908.06633 v1 pith:BMDCFLT4 submitted 2019-08-19 cs.FL cs.LO

Étienne André , Didier Lime , Mathias Ramparison This is my paper · ORCID

classification cs.FLcs.LO

keywords parametrictimedautomatainvariantsreachabilitysynthesisdecidabilityTCTLupper-boundconstraintsexactparameter

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a syntactic restriction of parametric timed automata in which transitions carry no guards, so timing constraints live only in location invariants. It shows that the unrestricted invariant-only version is still as expressive as full parametric timed automata and inherits their undecidability, but that a further restriction to upper-bound constraints makes the reachability (EF) emptiness problem decidable in NLOGSPACE and, more strongly, makes exact synthesis of all rational parameter valuations that reach a target location computable in exponential time. The paper also proves that full TCTL emptiness is undecidable for this same subclass, placing it at a boundary between decidability and undecidability. A small media-streaming case study illustrates the synthesis result.

What carries the argument

The central object is the class $\mathrm{PTA}^U_I$: parametric timed automata with no guards and with only upper-bound invariants, meaning every location constraint is of the form $x \lhd \sum_i \alpha_i p_i + d$ with $\lhd \in \{<,\leq\}$, $\alpha_i \in \{0,1\}$, and $d \in \mathbb{Z}$. The argument is carried by two lemmas showing that any successful run can be compressed to a zero-delay run, and that the existence of a zero-delay run is unchanged when each parameter is replaced while preserving whether it is zero or positive. This reduces EF-emptiness to NLOGSPACE reachability in a directed graph and EF-synthesis to enumerating $2^{|P|}$ representative parameter valuations.

What would settle it

Under the paper's own definition $d \in \mathbb{Z}$, let the target location have invariant $x < p - 2$ and no resets, with an unguarded edge from the initial location to it. For $p=3$ the location is immediately reachable because $x=0<1$; for $p=1$ the same sign pattern ($p>0$) gives the invariant $x < -1$, which no clock value can satisfy, so no run exists. This contradicts the paper's lemma that equal zero/nonzero patterns give equal reachability.

Watch

Extended reading notes

Core claim

The central discovery is a collapse in behavior: for a parametric timed automaton whose only constraints are upper-bound location invariants (each inequality of the form $x \lhd \sum_i \alpha_i p_i + d$ with $\lhd \in \{<,\leq\}$), the existence of some parameter valuation that reaches a given location is decided by zero-delay reachability in the non-parametric automaton where every parameter equals 1. More generally, whether a zero-delay path exists depends only on the zero/nonzero pattern of the parameter values, so the parameter space splits into at most $2^{|P|}$ regions. Testing one representative valuation per region yields an exact description of the EF-synthesis set, in exponential time and over unbounded rational parameters; the paper presents this as the first such exact synthesis result in this line of work without restrictions on clock count, parameter count, or resets.

Load-bearing premise

The whole construction depends on the assumption that two parameter choices with the same zero-versus-positive pattern always allow the same no-time-elapse paths; this requires the fixed integer offsets in upper-bound invariants never to make one such choice block a path that another choice in the same pattern admits.

Editorial extensions

If this is right

EF-emptiness for $\mathrm{PTA}^U_I$ is decidable in NLOGSPACE: it suffices to check zero-delay reachability in the automaton with all parameters set to 1.
EF-synthesis is exactly computable in exponential time, producing a finite union of regions of the form $p=0$ or $p>0$ for each parameter; this covers unbounded rational parameters.
Every guard can be compiled into an invariant by splitting the guarded edge into two unguarded edges through a fresh location, so invariant-only automata are as expressive as full PTAs and EF-emptiness for them is undecidable.
For bounded $\mathrm{PTA}^U_I$, the nested TCTL formula $\mathrm{EGAF}_{=0}$ can simulate a two-counter machine, making TCTL-emptiness undecidable in the class.
In the case study, the protocol's bad state is reachable under every valuation with $p_{\mathrm{send}}>0$ and $p_{\mathrm{rced}}>0$, while no valuation makes the bad state unavoidable on all runs.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The $2^{|P|}$-region classification works only if the integer offsets $d$ in upper-bound invariants are nonnegative; the paper never states this, and with a negative offset the equivalence fails: an invariant $x < p - 2$ admits a zero-delay run for $p=3$ but not for $p=1$, although both have $p>0$.
If the classification holds, every EF-synthesis set for $\mathrm{PTA}^U_I$ is a finite union of orthants defined by $p=0$ versus $p>0$, so the exact synthesis result has very simple geometry and could be checked by sign tests alone.
The guard-to-invariant compilation suggests a general recipe: for reachability questions, any PTA can be rewritten as an invariant-only automaton with twice as many edges, though undecidability of the target class means this translation cannot produce a decision procedure by itself.
A testable extension is whether AF-emptiness also respects the same zero/nonzero regions; the paper leaves flat TCTL formulas such as AF, EG, and AG open, and universal quantification over runs may break the collapse.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know two things about this paper. First, the central decidability and synthesis theorems for PTA^U_I are false as stated. Second, the mistake is localized and the paper is probably repairable.

The genuinely new idea is the guard-to-invariant encoding: a PTA without invariants can be turned into a PTA with only invariants, preserving reachability, so the invariant-only class inherits undecidability. I checked Lemma 1; it works. The paper then defines PTA^U_I, invariants of the form x ⊳ Σ α_i p_i + d, and claims EF-emptiness is NLOGSPACE and EF-synthesis can be computed exactly in exponential time by enumerating zero/nonzero patterns of valuations. That would be a real improvement over L/U-PTAs, which lack exact synthesis.

The problem is Definition 5. It allows d ∈ Z. The lemmas only hold if d ≥ 0. Here is a concrete failure: one clock x, one parameter p, initial location with no invariant, a single transition to goal with invariant x < p - 2. For v(p)=3, at clock value 0 the invariant x<1 holds, so the goal is reachable by a zero-delay run. For v'(p)=1, the invariant is x<-1, unsatisfiable for any nonnegative clock. Both valuations have the same zero/nonzero pattern, so Lemma 3's equivalence fails, and Lemma 2 fails too because v1(p)=1 gives the unsatisfiable invariant while v(p)=3 gives a satisfiable one. Hence Theorems 2 and 3 collapse. The exact synthesis set for this tiny automaton is p>2, not a union of zero-pattern regions.

If the authors restrict d to N, the monotonicity argument goes through: with d≥0, satisfiability of an upper-bound invariant at clock value 0 is determined exactly by whether the expression is zero or positive, which is the zero-pattern information. So the claimed results are likely recoverable by a small syntactic repair. That does not rescue the paper as written; the counterexample is directly under the stated definition, and the proofs of Lemmas 2 and 3 explicitly rely on the false claim that nothing can block a zero-delay run. The TCTL undecidability reduction uses only nonnegative offsets, so it is not affected.

Who is this for? People working on parametric timed automata who care about subclass taxonomy and exact synthesis. The paper is clearly written and the failure mode is instructive. It deserves peer review because the idea is valuable and the fix is identifiable, but the current version should be rejected or returned for revision.

Referee Report

2 major / 3 minor

Summary. The paper introduces a syntactic subclass of parametric timed automata called PTA^U_I, in which transitions have no guards and location invariants are restricted to upper-bound constraints of the form x ⊳ Σ α_i p_i + d. It claims three main results: (1) arbitrary PTAs can be encoded by invariant-only automata, so EF-emptiness remains undecidable for PTAs with only invariants; (2) for PTA^U_I, EF-emptiness is decidable in NLOGSPACE and exact EF-synthesis is computable in exponential time by testing one valuation per zero/nonzero parameter pattern; and (3) TCTL-emptiness, in particular EGAF=0-emptiness, is undecidable for bounded PTA^U_I. The paper also reports a small case study of a media streaming protocol.

Significance. If the central results were correct, the paper would be significant: it would give the first exact EF-synthesis over unbounded rational-valued parameters for a nontrivial subclass of PTAs, at exponential cost, together with an undecidability boundary for TCTL. The guard-to-invariant translation in Section III is clean and appears correct, and the TCTL gadget construction in Section IV.B is substantial. However, the decidability and synthesis claims are false under the paper's own definitions. The root cause is that Definition 5 allows constant offsets d ∈ Z, including negative offsets, while Lemmas 2 and 3 assume only the zero/nonzero pattern of parameters matters. A one-clock, one-parameter counterexample directly contradicts both lemmas and invalidates the algorithm of Theorem 3. As stated, the paper's main positive contribution is not defensible.

major comments (2)

[§IV.A, Definition 5 and Lemma 2] Lemma 2 is false under the syntax actually defined in the paper. Definition 5 allows invariants of the form x ⊳ Σ α_i p_i + d with d ∈ Z, and Section II.A defines d ∈ Z with no nonnegativity restriction. The proof of Lemma 2 only discusses blockers of the form x < p with v(p) = 0 and then concludes that v1(A) has no blocking invariant because all parameters evaluate to 1; this ignores negative constant offsets. Concretely, let A have locations ℓ0 and ℓf, an unguarded transition ℓ0 → ℓf, and invariant I(ℓf) : x < p − 2. For v(p) = 3, the transition can be taken at clock value 0 because x < 1 holds, so ℓf is reachable. For v1(p) = 1, the invariant becomes x < −1, which no nonnegative clock valuation satisfies, so ℓf is unreachable. Thus the equivalence in Lemma 2 fails, and the NLOGSPACE decision procedure of Theorem 2, which tests only v1(A) using a syntactic check for invariants of the form x < 0, is not a correct decision procedure for EF-emptiness of PTA^U_I as defined.
[§IV.A, Lemma 3 and Theorem 3] Lemma 3 is also false, and this invalidates the EF-synthesis claim of Theorem 3. Using the same automaton as in the previous comment, take v(p) = 3 and v'(p) = 1. The two valuations are equivalent under Definition 6 because both parameters are positive. There is a zero-delay run reaching ℓf in v(A), since x = 0 satisfies x < 1, but there is no run in v'(A) reaching ℓf, since the invariant x < −1 is unsatifiable for all nonnegative clock values. Therefore the zero/nonzero pattern of parameter values does not determine reachability, and the 2^{|P|} regions of Definition 6 do not refine the exact synthesis set. For this automaton the exact EF-synthesis set is {v ∈ Q+ | v(p) > 2}, which is neither of the regions p = 0 or p > 0. The argument would go through under an additional restriction d ≥ 0, but no such restriction appears in Definition 5 or anywhere else in Section II.

minor comments (3)

[§V, final paragraph] The text says 'we focus on EF(askMore, notSending)-synthesis' and then states that the result is 'the set of valuations for which all runs eventually reach' the location; that property is AF, not EF, so the modal terminology should be corrected.
[Definition 2] The definition lists S = {(ℓ,w) ∈ L × R_+^H | w |= v(I(ℓ))} and then separately lists s0 = (ℓ0, ⃗0); it should state explicitly that the initial state is required to belong to S, or that the initial invariant is assumed satisfiable.
[Lemma 1 proof] The sentence 'Once in ℓ1′, we cannot stay forever because of I(ℓ1′)' is not literally true for tautological guards such as x ≥ 0; the induction only needs the run to take the second transition immediately, so the sentence should be reworded to avoid claiming that the invariant forces progress.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the exact-synthesis proof derives from a semantic lemma and the reused [ALR16] encoding is external support, not a self-citation chain.

full rationale

Walking the derivation chain, the central claims are not circular. Theorem 3 is derived from Lemma 3, which asserts a semantic equivalence for valuations with the same zero/nonzero pattern; Lemma 3 is not Definition 6 restated, and its proof attempts an independent argument from the PTA^U_I invariant syntax, so the synthesis result does not reduce by construction to its inputs. Lemma 2 and Theorem 2 similarly rely on a semantic argument about zero-delay runs, not on the target claim. The undecidability proof in Section IV-B reuses the encoding of [ALR16], but as a cited, published construction applied to a different formalism and claim, with the PTA^U_I-specific gadgets verified in the present paper; this is legitimate external support rather than a self-citation chain. The flagged defect that constants d in Z may be negative, for example an invariant x < p - 2, undermines Lemmas 2 and 3 and therefore Theorems 2 and 3, but that is a soundness or correctness problem, not circularity: the lemma's conclusion is neither stipulated by the definition of the equivalence relation nor forced by any fitted parameter. No fitted input is renamed as a prediction, and no load-bearing claim reduces to a prior result of the same authors that is itself unverified. Hence the paper is not circular, and the score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central proofs rest on three standard prior results and one hidden assumption. The hidden assumption is that constant offsets in upper-bound invariants are nonnegative or irrelevant; this is load-bearing because Lemmas 2 and 3 fail for negative offsets. No free parameters are fitted, and no new entities are invented.

assumptions (4)

standard math EF-emptiness is undecidable for PTAs without invariants.
Used in Theorem 1 to transfer undecidability to PTAI via the guard-to-invariant transformation; cited as [AHV93].
standard math The boundedness problem for two-counter machines is undecidable.
Basis for the EGAF=0 undecidability reduction in Theorem 4; cited as [KC10].
standard math Reachability in a directed graph is decidable in NLOGSPACE.
Used in the proof of Theorem 2 to decide zero-delay reachability; cited as [Pap94].
ad hoc to paper Constant offsets d in upper-bound invariants are nonnegative or otherwise do not affect zero-delay reachability.
Implicit in Lemmas 2 and 3 and in the 0/1-valuation synthesis algorithm; Definition 5 allows d in Z, so the assumption is load-bearing and currently unstated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the expressive power of invariants in parametric timed automata." pith.science (2026). https://pith.science/paper/BMDCFLT4

@misc{pith2026190806633,
  author       = {Pith},
  title        = {Pith review of: On the expressive power of invariants in parametric timed automata},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BMDCFLT4}},
  note         = {Machine review of arXiv:1908.06633}
}

read the original abstract

The verification of systems combining hard timing constraints with concurrency is challenging. This challenge becomes even harder when some timing constants are missing or unknown. Parametric timed formalisms, such as parametric timed automata (PTAs), tackle the synthesis of such timing constants (seen as parameters) for which a property holds. Such formalisms are highly expressive, but also undecidable, and few decidable subclasses were proposed. We propose here a syntactic restriction on PTAs consisting in removing guards (constraints on transitions) to keep only invariants (constraints on locations). While this restriction preserves the expressiveness of PTAs (and therefore their undecidability), an additional restriction on the type of constraints allows to not only prove decidability, but also to perform the exact synthesis of parameter valuations satisfying reachability. This formalism, that seems trivial at first sight as it benefits from the decidability of the reachability problem with a better complexity than Timed Automata (TAs), suffers from the undecidability of the whole TCTL logic that TAs, on the contrary enjoy. We believe our formalism allows for an interesting trade-off between decidability and practical expressiveness and is therefore promising. We show its applicability in a small case study.

Figures

Figures reproduced from arXiv: 1908.06633 by the authors.

**Figure 2.** A gadget fragment and its modification into a [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** increment gadget Given v, our encoding is such that when in ℓ i with w(z) = 0 then w(x1) (resp. w(x2)) represents the value of the counter c1 (resp. c2) encoded by 1−v(a)c1 (resp. 1−v(a)c2) with v(a) small enough so v(a)c1 < 1 (resp. v(a)c2 < 1). The two branches in the gadgets handle both cases w(x1) > w(x2) and w(x1) ≤ w(x2). b) Increment gadget: Depicted in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: decrement gadget ℓ0 ℓ 1 0 z = 0 x1 ≤ 1 x2 ≤ 1 ℓ 2 0 z = 0 x1 < 1 x2 < 1 ℓerror ℓ1 [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]

**Figure 5.** Figure 5: initialisation gadget a) Software support: PTAsU I are natively supported by IMITATOR [And+12], which is a parametric model checker performing parameter synthesis for parametric timed automata, extended with some useful features such as synchronization, global variable…

**Figure 6.** Figure 6: Model of a media streaming protocol from start is similar to the previously described one. From locations askMore,sending and idle, notSending the location askMore, notSending is reachable, when the server is not streaming and the client’s buffer is empty. This is the …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 2 canonical work pages

[1]

Model-Checking in Dense Real-Time

[ACD93] Rajeev Alur, Costas Courcoubetis, and David L. Dill . “Model-Checking in Dense Real-Time”. In: Information and Computation 104.1 (May 1993), pp. 2–34 . DOI : 10.1006/inco.1993.1024 (cit. on pp. 3, 8). [AD94] Rajeev Alur and David L. Dill. “A theory of timed automata”. In: Theoretical Computer Science 126.2 (Apr. 1994), pp. 183–235. ISSN : 0304-397...

arXiv 1993
[1790]

Pittsburgh, PA, USA: Springer, 2000, pp

Lecture Notes in Computer Science. Pittsburgh, PA, USA: Springer, 2000, pp. 296–309. ISBN : 3-540-67259-1 . DOI : 10.1007/3-540-46430-1 26 (cit. on p. 1). [Pap94] Christos H. Papadimitriou. Computational complexity . Addison-Wesley,

work page doi:10.1007/3-540-46430-1 2000
[3098]

Robust Parametric Reachability fo r Timed Automata

Lecture Notes in Computer Sci- ence. Eichst¨ att, Germany: Springer, 2003, pp. 87–124 . DOI : 10.1007/978-3-540-27755-2 3 (cit. on p. 5). [Doy07] Laurent Doyen. “Robust Parametric Reachability fo r Timed Automata”. In: Information Processing Letters 102.5 (2007), pp. 208–213 . DOI : 10.1016/j.ipl.2006.11.018 (cit. on p. 1). [Hun+02] Thomas Hune, Judi Romi...

work page arXiv 2007
[7436]

What’s decidable about parametric timed automata?

Lecture Notes in Computer Science. Paris, France: Springer, Aug. 2012, pp. 33–36 . DOI : 10.1007/978-3-642-32759-9 6 (cit. on p. 8). [And19] ´Etienne Andr´ e. “What’s decidable about parametric timed automata?” In: International Journal on Soft- ware Tools for Technology Transfer 21.2 (Apr. 2019), pp. 203–219 . DOI : 10.1007/s10009-017-0467-0 (cit. on p. ...

doi:10.1007/978-3-642-32759-9 2012
[8634]

Timed Automata: Semantics, Algorithms and Tools

Lecture Notes in Computer Science. Budapest, Hungary: Springer, 2014, pp. 123–134. ISBN : 978-3-662-44521-1 . DOI : 10.1007/978-3-662-44522-8 (cit. on pp. 1, 2). [BY03] Johan Bengtsson and Wang Yi. “Timed Automata: Semantics, Algorithms and Tools”. In: Lectures on Concurrency and Petri Nets, Advances in Petri Nets . Ed. by J¨ org Desel, Wolfgang Reisig, a...

doi:10.1007/978-3-662-44522-8 2014
[9135]

Decision problems for lower/upper bound parametric timed au- tomata

Lecture Notes in Computer Sci- ence. Kyoto, Japan: Springer, 2015, pp. 69–81 . DOI : 10.1007/978-3-662-47666-6 6 (cit. on pp. 1, 2). [BL09] Laura Bozzelli and Salvatore La Torre. “Decision problems for lower/upper bound parametric timed au- tomata”. In: F ormal Methods in System Design 35.2 (2009), pp. 121–151 . DOI : 10.1007/s10703-009-0074-0 (cit. on pp...

doi:10.1007/978-3-662-47666-6 2009

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Model-Checking in Dense Real-Time

[ACD93] Rajeev Alur, Costas Courcoubetis, and David L. Dill . “Model-Checking in Dense Real-Time”. In: Information and Computation 104.1 (May 1993), pp. 2–34 . DOI : 10.1006/inco.1993.1024 (cit. on pp. 3, 8). [AD94] Rajeev Alur and David L. Dill. “A theory of timed automata”. In: Theoretical Computer Science 126.2 (Apr. 1994), pp. 183–235. ISSN : 0304-397...

arXiv 1993

[2] [1790]

Pittsburgh, PA, USA: Springer, 2000, pp

Lecture Notes in Computer Science. Pittsburgh, PA, USA: Springer, 2000, pp. 296–309. ISBN : 3-540-67259-1 . DOI : 10.1007/3-540-46430-1 26 (cit. on p. 1). [Pap94] Christos H. Papadimitriou. Computational complexity . Addison-Wesley,

work page doi:10.1007/3-540-46430-1 2000

[3] [3098]

Robust Parametric Reachability fo r Timed Automata

Lecture Notes in Computer Sci- ence. Eichst¨ att, Germany: Springer, 2003, pp. 87–124 . DOI : 10.1007/978-3-540-27755-2 3 (cit. on p. 5). [Doy07] Laurent Doyen. “Robust Parametric Reachability fo r Timed Automata”. In: Information Processing Letters 102.5 (2007), pp. 208–213 . DOI : 10.1016/j.ipl.2006.11.018 (cit. on p. 1). [Hun+02] Thomas Hune, Judi Romi...

work page arXiv 2007

[4] [7436]

What’s decidable about parametric timed automata?

Lecture Notes in Computer Science. Paris, France: Springer, Aug. 2012, pp. 33–36 . DOI : 10.1007/978-3-642-32759-9 6 (cit. on p. 8). [And19] ´Etienne Andr´ e. “What’s decidable about parametric timed automata?” In: International Journal on Soft- ware Tools for Technology Transfer 21.2 (Apr. 2019), pp. 203–219 . DOI : 10.1007/s10009-017-0467-0 (cit. on p. ...

doi:10.1007/978-3-642-32759-9 2012

[5] [8634]

Timed Automata: Semantics, Algorithms and Tools

Lecture Notes in Computer Science. Budapest, Hungary: Springer, 2014, pp. 123–134. ISBN : 978-3-662-44521-1 . DOI : 10.1007/978-3-662-44522-8 (cit. on pp. 1, 2). [BY03] Johan Bengtsson and Wang Yi. “Timed Automata: Semantics, Algorithms and Tools”. In: Lectures on Concurrency and Petri Nets, Advances in Petri Nets . Ed. by J¨ org Desel, Wolfgang Reisig, a...

doi:10.1007/978-3-662-44522-8 2014

[6] [9135]

Decision problems for lower/upper bound parametric timed au- tomata

Lecture Notes in Computer Sci- ence. Kyoto, Japan: Springer, 2015, pp. 69–81 . DOI : 10.1007/978-3-662-47666-6 6 (cit. on pp. 1, 2). [BL09] Laura Bozzelli and Salvatore La Torre. “Decision problems for lower/upper bound parametric timed au- tomata”. In: F ormal Methods in System Design 35.2 (2009), pp. 121–151 . DOI : 10.1007/s10703-009-0074-0 (cit. on pp...

doi:10.1007/978-3-662-47666-6 2009