Decidability Boundaries in Priced Timed Automata

18 concepts4 papers1 proposal

Timed automata are a foundational formalism for verifying real-time systems, tracking the passage of time via continuous variables called "clocks." However, real-world systems do not just consume time; they consume physical resources like energy, bandwidth, or financial cost. To capture these dynamics, researchers introduced Priced Timed Automata (PTAs). As described by Uli Fahrenberg et al. in Quantitative analysis of real-time systems using priced timed automata, PTAs augment standard timed automata by mapping cost rates to states and discrete costs to transitions.

The core challenge in PTAs is balancing expressiveness with decidability. Clocks and costs are both continuous variables that grow over time. If they interact too freely, the state space becomes unmanageably infinite, allowing the system to simulate a Turing-complete machine. To prevent this, costs are typically treated as observer variables—they accumulate resource usage along a path but do not directly steer the automaton's control flow or transition guards. Yet, even as observers, verifying properties that bound these costs pushes algorithmic verification to its absolute limits.

The Razor-Thin Decidability Boundary

When we want to verify properties over a system's cost—such as "can the system complete its task within a certain budget?"—the boundary between what is automatically verifiable (decidable) and what is mathematically impossible to verify (undecidable) is incredibly sharp.

In Model-Checking One-Clock Priced Timed Automata and its expanded analysis in Model Checking One-Clock Priced Timed Automata, Nicolas Markey et al. mapped this boundary across different temporal logics. They demonstrated that for branching-time properties expressed in Weighted Computation Tree Logic (WCTL), model checking remains PSPACE-complete if the automaton is restricted to a single clock. This matches the complexity of standard timed automata, meaning that tracking a linear cost variable introduces no theoretical performance penalty for branching-time verification.

However, when moving to linear-time properties via Weighted Metric Temporal Logic (WMTL), the problem becomes highly volatile. The authors proved that WMTL model checking is decidable only under a hyper-constrained configuration: the system must have exactly one clock and exactly one "stopwatch" cost variable, where costs accumulate at a binary rate of either 0 or 1.

Why is this boundary so fragile? The intuition lies in how undecidability is established. Nicolas Markey et al. showed that relaxing these constraints—either by adding a second clock or allowing a general cost variable with arbitrary rates—allows the system to simulate a two-counter Minsky machine.

Standard PTA:  [Clock 1] ----\
               [Clock 2] ----+---> Can synchronize to encode unbounded counters (Undecidable)
               [Cost Var] ---/

Restricted:    [Clock 1] ----\____ No second clock to cross-reference;
               [Stopwatch] --/     cannot isolate fractional values (Decidable)

With two independent clocks and a cost variable, an automaton can use the time elapsed in one state to precisely copy, scale, and transfer fractional values between variables. This cross-talk allows the system to store and manipulate discrete, unbounded values, effectively turning continuous time into a digital memory tape. Restricting the architecture to a single clock and a stopwatch cost eliminates the geometric degrees of freedom needed to isolate and manipulate these fractional values, blocking the simulation of a counter machine and preserving decidability.

Scaling to Realistic Costs with Piecewise-Linear Functions

While the theoretical boundaries for temporal logic verification are restrictive, practical engineering requires modeling complex, non-constant cost behaviors. For instance, a drone's battery drains faster under heavy aerodynamic load, or electricity costs change depending on the time of day.

If general nonlinear cost functions are introduced, the optimal reachability problem immediately becomes undecidable because nonlinear curves can easily encode complex arithmetic constraints. However, Devendra Bhave et al. identified a powerful loophole in On Nonlinear Prices in Timed Automata. They demonstrated that incorporating piecewise-linear cost functions does not increase the computational complexity of the reachability problem beyond that of standard linear models.

To understand why this works, consider how timed automata verification algorithms operate. They do not track every infinite real-valued timestamp; instead, they group states into a finite set of polyhedral regions called "zones," defined by linear inequalities between clocks (e.g., $x - y \le 2$).

Because a piecewise-linear function consists of a finite sequence of straight-line segments, the state space of the automaton can be subdivided into regions where each cost rate is temporarily constant. Within each segment, the cost accumulates linearly, perfectly preserving the underlying polyhedral geometry of the clock zones.

By reframing variable cost rates as a sequence of discrete, linear phases, the authors showed that modern Satisfiability Modulo Theories (SMT) solvers can navigate these segmented zones natively. This allows practitioners to model highly realistic, variable-rate resource consumption without triggering the theoretical penalties or undecidability traps of fully nonlinear systems.

Key Foundational Work

Model Checking One-Clock Priced Timed Automata (2008) — contributed 8 concept elements to this direction.
Model-Checking One-Clock Priced Timed Automata (2007) — contributed 8 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_piecewise_linear_cost_complexity_f4a354c9,
  title = {piecewise-linear cost complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/piecewise-linear-cost-complexity/rdr_f4a354c98ca14bcdb25f994aadd9af00},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_piecewise_linear_cost_complexity_f4a354c9_v1,
  title = {piecewise-linear cost complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/piecewise-linear-cost-complexity/rdr_f4a354c98ca14bcdb25f994aadd9af00/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake