2026-07-22T16:58:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9907 2024-03-06T10:45:05Z ddc:004 open_access

Verification of Timed Asynchronous Programs Abdulla, Parosh Aziz Atig, Mohamed Faouzi Krishna, Shankara Narayanan Vaidya, Shaan Reachability Timed Automata Asynchronous programs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Parosh Aziz Abdulla and Mohamed Faouzi Atig and Shankara Narayanan Krishna and Shaan Vaidya 2018 Is Part Of LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2018.8 urn:nbn:de:0030-drops-99076 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.8 eng https://creativecommons.org/licenses/by/3.0/legalcode