EUVIMEDSkopri EUVIMED
Crossref

Cost-Optimal Reachability for Timed Automata with Diagonals via Zone Simulations

Sayan Mukherjee

Bulletin of Computer and Data Sciences · 2020

DOI: 10.71448/bcds2011-2 ↗

At a glance

Journal article in Bulletin of Computer and Data Sciences, 2020. Written by Sayan Mukherjee.

AstrattDettalji biblijografiċiCiteRelated studies

Abstract (original language)

We study cost-optimal reachability in priced timed automata whose guards and invariants may include diagonal constraints of the form x−y⌣c. Classical extrapolation and zone-splitting approaches struggle with diagonals, often incurring exponential blow-ups or losing optimality guarantees. We propose a simulation-based priced zone exploration that (i) keeps actual zones with diagonals, (ii) propagates sound lower bounds on accumulated cost, and (iii) prunes the search using an antichain partial order combining zone simulation with cost dominance. We derive admissible A∗-style heuristics from dynamic LU bounds generalized to diagonals, and we prove soundness and conditional termination for subclasses where the induced abstraction has finitely many antichain minima. An implementation evaluates diagonal-heavy scheduling and protocol benchmarks against diagonal-free conversion and state-of-the-art priced engines. Experiments show consistent reductions in explored nodes and time while preserving optimal costs, enabling cost-optimal analysis on models previously intractable under diagonal splitting.

Cite

APA

Mukherjee, S. (2020). Cost-Optimal Reachability for Timed Automata with Diagonals via Zone Simulations. Bulletin of Computer and Data Sciences. https://doi.org/10.71448/bcds2011-2

Vancouver

Mukherjee S. Cost-Optimal Reachability for Timed Automata with Diagonals via Zone Simulations. Bulletin of Computer and Data Sciences. 2020. doi:10.71448/bcds2011-2

BibTeX
@article{Mukherjee2020,
  author = {Mukherjee, Sayan},
  title = {Cost-Optimal Reachability for Timed Automata with Diagonals via Zone Simulations},
  journal = {Bulletin of Computer and Data Sciences},
  year = {2020},
  doi = {10.71448/bcds2011-2}
}
Start for free →