Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1790538,
author = {Ajdarów, Michal and Kučera, Antonín},
address = {Dagstuhl, Germany},
booktitle = {32nd International Conference on Concurrency Theory (CONCUR 2021)},
doi = {http://dx.doi.org/10.4230/LIPIcs.CONCUR.2021.30},
editor = {Haddad, Serge and Varacca, Daniele},
keywords = {VASS; termination complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Dagstuhl, Germany},
isbn = {978-3-95977-203-7},
pages = {"30:1"-"30:15"},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik},
title = {Deciding Polynomial Termination Complexity for VASS Programs},
url = {https://drops.dagstuhl.de/opus/volltexte/2021/14407},
year = {2021}
}
TY - JOUR
ID - 1790538
AU - Ajdarów, Michal - Kučera, Antonín
PY - 2021
TI - Deciding Polynomial Termination Complexity for VASS Programs
PB - Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
CY - Dagstuhl, Germany
SN - 9783959772037
KW - VASS
KW - termination complexity
UR - https://drops.dagstuhl.de/opus/volltexte/2021/14407
N2 - We show that for every fixed degree k ≥ 3, the problem whether the termination/counter complexity of a given demonic VASS is O(n^k), Ω(n^k), and Θ(n^k) is coNP-complete, NP-complete, and DP-complete, respectively. We also classify the complexity of these problems for k ≤ 2. This shows that the polynomial-time algorithm designed for strongly connected demonic VASS in previous works cannot be extended to the general case. Then, we prove that the same problems for VASS games are PSPACE-complete. Again, we classify the complexity also for k ≤ 2. Tractable subclasses of demonic VASS and VASS games are obtained by bounding certain structural parameters, which opens the way to applications in program analysis despite the presented lower complexity bounds.
ER -
AJDARÓW, Michal and Antonín KUČERA. Deciding Polynomial Termination Complexity for VASS Programs. Online. In Haddad, Serge and Varacca, Daniele. \textit{32nd International Conference on Concurrency Theory (CONCUR 2021)}. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, 2021, p.~''30:1''-''30:15'', 15 pp. ISBN~978-3-95977-203-7. Available from: https://dx.doi.org/10.4230/LIPIcs.CONCUR.2021.30.
|
