Deciding Polynomial Termination Complexity for VASS Programs

@inproceedings{45606,
   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},
   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  - 45606
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 a Antonín KUČERA. Deciding Polynomial Termination Complexity for VASS Programs. In \textit{32nd International Conference on Concurrency Theory (CONCUR 2021)}. Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, 2021. s.~''30:1-30:15'', 15 s. ISBN~978-3-95977-203-7. doi:10.4230/LIPIcs.CONCUR.2021.30.