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.2018.8
URN: urn:nbn:de:0030-drops-99076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9907/
Go to the corresponding LIPIcs Volume Portal

Abdulla, Parosh Aziz ; Atig, Mohamed Faouzi ; Krishna, Shankara Narayanan ; Vaidya, Shaan

Verification of Timed Asynchronous Programs

pdf-format:
LIPIcs-FSTTCS-2018-8.pdf (0.5 MB)

Abstract

In this paper, we address the verification problem for timed asynchronous programs. We associate to each task, a deadline for its execution. We first show that the control state reachability problem for such class of systems is decidable while the configuration reachability problem is undecidable. Then, we consider the subclass of timed asynchronous programs where tasks are always being executed from the same state. For this subclass, we show that the control state reachability problem is PSPACE-complete. Furthermore, we show the decidability for the configuration reachability problem for the subclass.

BibTeX - Entry

@InProceedings{abdulla_et_al:LIPIcs:2018:9907,
  author =	{Parosh Aziz Abdulla and Mohamed Faouzi Atig and Shankara Narayanan Krishna and Shaan Vaidya},
  title =	{{Verification of Timed Asynchronous Programs}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9907},
  URN =		{urn:nbn:de:0030-drops-99076},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.8},
  annote =	{Keywords: Reachability, Timed Automata, Asynchronous programs}
}

Keywords: Reachability, Timed Automata, Asynchronous programs
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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