Deciding Polynomial Termination Complexity for VASS Programs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00119194" target="_blank" >RIV/00216224:14330/21:00119194 - isvavai.cz</a>
Result on the web
<a href="https://drops.dagstuhl.de/opus/volltexte/2021/14407" target="_blank" >https://drops.dagstuhl.de/opus/volltexte/2021/14407</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.CONCUR.2021.30" target="_blank" >10.4230/LIPIcs.CONCUR.2021.30</a>

Result language
angličtina
Original language name
Deciding Polynomial Termination Complexity for VASS Programs
Original language description
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.
Czech name
—
Czech description
—

Project
<a href="/en/project/GA21-24711S" target="_blank" >GA21-24711S: Efficient Analysis and Optimization for Probabilistic Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2021
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
32nd International Conference on Concurrency Theory (CONCUR 2021)
ISBN
9783959772037
ISSN
1868-8969
e-ISSN
—
Number of pages
15
Pages from-to
„30:1“-„30:15“
Publisher name
Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Place of publication
Dagstuhl, Germany
Event location
Paris, France
Event date
Aug 23, 2021
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)