License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.47
URN: urn:nbn:de:0030-drops-132881
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13288/
Go to the corresponding LIPIcs Volume Portal

Gastin, Paul ; Mukherjee, Sayan ; Srivathsan, B

Reachability for Updatable Timed Automata Made Faster and More Effective

pdf-format:
LIPIcs-FSTTCS-2020-47.pdf (0.5 MB)

Abstract

Updatable timed automata (UTA) are extensions of classical timed automata that allow special updates to clock variables, like x: = x - 1, x : = y + 2, etc., on transitions. Reachability for UTA is undecidable in general. Various subclasses with decidable reachability have been studied. A generic approach to UTA reachability consists of two phases: first, a static analysis of the automaton is performed to compute a set of clock constraints at each state; in the second phase, reachable sets of configurations, called zones, are enumerated. In this work, we improve the algorithm for the static analysis. Compared to the existing algorithm, our method computes smaller sets of constraints and guarantees termination for more UTA, making reachability faster and more effective. As the main application, we get an alternate proof of decidability and a more efficient algorithm for timed automata with bounded subtraction, a class of UTA widely used for modelling scheduling problems. We have implemented our procedure in the tool TChecker and conducted experiments that validate the benefits of our approach.

BibTeX - Entry

@InProceedings{gastin_et_al:LIPIcs:2020:13288,
  author =	{Paul Gastin and Sayan Mukherjee and B Srivathsan},
  title =	{{Reachability for Updatable Timed Automata Made Faster and More Effective}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13288},
  URN =		{urn:nbn:de:0030-drops-132881},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.47},
  annote =	{Keywords: Updatable timed automata, Reachability, Zones, Simulations, Static analysis}
}

Keywords: Updatable timed automata, Reachability, Zones, Simulations, Static analysis
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI