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.
|