← News

ResearchSources: arXiv · 18 Nov 2026

SYMAR speeds probabilistic timed automata verification in PRISM benchmarks

A new arXiv paper introduces SYMAR, a symbolic refinement method for verifying probabilistic timed automata, reporting large speedups over PRISM's existing approach on standard benchmarks.

In plain words

Autonomous systems must make decisions under uncertainty and deadlines, and probabilistic timed automata are models used to check how reliably such decisions reach goals or avoid hazards. The SYMAR method keeps probability information attached to each model state symbolically, so it avoids repeatedly splitting states and rebuilding transitions. In the paper's benchmarks, this made verification much faster than the existing PRISM-based method.

What was announced

The authors present SYMAR, a refinement method that makes the value function symbolic: each symbolic state carries a function mapping sub-regions of its clock region to probability bounds, so refinement appears as new sub-regions rather than splitting existing states or reconstructing their incoming transitions. According to the paper, both sources of nondeterminism in these models, timing and action choice, are handled implicitly by the preimage computation that produces those sub-regions. A heuristic forward search expands an And-Or graph from the initial state along promising behaviors, confining effort to the property-relevant fragment, while a partial-refinement backup keeps the sub-region count manageable. The authors state that every stored interval provably contains the true probability.

On the PRISM PTA benchmarks, which the paper says cover subproblems recurring in autonomous systems such as distributed agreement, leader election, and self-configuration, SYMAR is reported up to 108x faster than the existing method. It also solves one instance where the existing method exhausts the time limit, and shows less sensitivity to deadline constants: one instance is resolved in a 37-node search graph unchanged as the deadline triples, whereas the existing method reportedly needs 86,380 abstract states and 73 refinement rounds. These figures come from the authors' own evaluation and have not been independently confirmed.

What it does not show

  • The evidence is limited to the paper's abstract; full technical details, experimental setup, and peer review status are not available from this source.
  • All performance claims, including the 108x speedup and specific state counts, are reported by the authors and not independently verified.

Sources

Source-support review completed 19 Nov 2026. This story was drafted with AI assistance and checked against retained source passages. Automated checking is not independent verification.

Coverage: arXiv: abstract.

Updates and corrections

No corrections so far.

First published 19 Nov 2026

New to the subject? AI from the Ground Up starts from the beginning.