Cost-Optimal Reachability for Timed Automata with Diagonals via Zone Simulations
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.
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}
}
EUVIMED