AJDARÓW, Michal and Antonín KUČERA. Deciding Polynomial Termination Complexity for VASS Programs. In 32nd International Conference on Concurrency Theory (CONCUR 2021). Dagstuhl, Germany: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik. p. "30:1"-"30:15", 15 pp. ISBN 978-3-95977-203-7. doi:10.4230/LIPIcs.CONCUR.2021.30. 2021.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Deciding Polynomial Termination Complexity for VASS Programs
Authors AJDARÓW, Michal and Antonín KUČERA.
Edition Dagstuhl, Germany, 32nd International Conference on Concurrency Theory (CONCUR 2021), p. "30:1"-"30:15", 15 pp. 2021.
Publisher Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Other information
Original language English
Type of outcome Proceedings paper
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
Organization Fakulta informatiky – Repository – Repository
ISBN 978-3-95977-203-7
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2021.30
Keywords (in Czech) VASS; výpočetní složitost
Keywords in English VASS; termination complexity
Links GA21-24711S, research and development project. MUNI/A/1108/2020, interní kód Repo. MUNI/A/1549/2020, interní kód Repo.
Changed by Changed by: RNDr. Daniel Jakubík, učo 139797. Changed: 29/4/2022 03:09.
Abstract
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.
Type Name Uploaded/Created by Uploaded/Created Rights
LIPIcs-CONCUR-2021-30.pdf Licence Creative Commons  File version 9/9/2021

Properties

Name
LIPIcs-CONCUR-2021-30.pdf
Address within IS
https://repozitar.cz/auth/repo/45606/1139522/
Address for the users outside IS
https://repozitar.cz/repo/45606/1139522/
Address within Manager
https://repozitar.cz/auth/repo/45606/1139522/?info
Address within Manager for the users outside IS
https://repozitar.cz/repo/45606/1139522/?info
Uploaded/Created
Thu 9/9/2021 02:00

Rights

Right to read
  • anyone on the Internet
Right to upload
 
Right to administer:
  • a concrete person Mgr. Lucie Vařechová, uco 106253
  • a concrete person RNDr. Daniel Jakubík, uco 139797
  • a concrete person Mgr. Jolana Surýnková, uco 220973
Attributes
 
Print
Add to clipboard Displayed: 29/3/2024 13:25