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.2016.48
URN: urn:nbn:de:0030-drops-68831
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6883/
Herbreteau, Frédéric ; Srivathsan, B. ; Tran, Thanh-Tung ; Walukiewicz, Igor
Why Liveness for Timed Automata Is Hard, and What We Can Do About It
| pdf-format: |
|
Abstract
The liveness problem for timed automata asks if a given automaton has a run passing infinitely often through an accepting state. We show that unless P=NP, the liveness problem is more difficult than the reachability problem; more precisely, we exhibit a family of automata for which solving the reachability problem with the standard algorithm is in P but solving the liveness problem is NP-hard. This leads us to revisit the algorithmics for the liveness problem. We propose a notion of a witness for the fact that a timed automaton violates a liveness property. We give an algorithm for computing such a witness and compare it with the existing solutions.
BibTeX - Entry
@InProceedings{herbreteau_et_al:LIPIcs:2016:6883,
author = {Fr{\'e}d{\'e}ric Herbreteau and B. Srivathsan and Thanh-Tung Tran and Igor Walukiewicz},
title = {{Why Liveness for Timed Automata Is Hard, and What We Can Do About It}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {48:1--48:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6883},
URN = {urn:nbn:de:0030-drops-68831},
doi = {10.4230/LIPIcs.FSTTCS.2016.48},
annote = {Keywords: Timed automata, model-checking, liveness invariant, state subsumption}
}
| Keywords: | Timed automata, model-checking, liveness invariant, state subsumption | |
| Seminar: | 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 10.12.2016 |
