AJDARÓW, Michal a 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. s. "30:1"-"30:15", 15 s. ISBN 978-3-95977-203-7. doi:10.4230/LIPIcs.CONCUR.2021.30. 2021.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Deciding Polynomial Termination Complexity for VASS Programs
Autoři AJDARÓW, Michal a Antonín KUČERA.
Vydání Dagstuhl, Germany, 32nd International Conference on Concurrency Theory (CONCUR 2021), od s. "30:1"-"30:15", 15 s. 2021.
Nakladatel Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Další údaje
Originální jazyk angličtina
Typ výsledku Stať ve sborníku
Stát vydavatele Německo
Utajení není předmětem státního či obchodního tajemství
Forma vydání elektronická verze "online"
WWW URL
Organizace Fakulta informatiky – Masarykova univerzita – Repozitář
ISBN 978-3-95977-203-7
ISSN 1868-8969
Doi http://dx.doi.org/10.4230/LIPIcs.CONCUR.2021.30
Klíčová slova česky VASS; výpočetní složitost
Klíčová slova anglicky VASS; termination complexity
Návaznosti GA21-24711S, projekt VaV. MUNI/A/1108/2020, interní kód Repo. MUNI/A/1549/2020, interní kód Repo.
Změnil Změnil: RNDr. Daniel Jakubík, učo 139797. Změněno: 29. 4. 2022 03:09.
Anotace
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.
Typ Název Vložil/a Vloženo Práva
LIPIcs-CONCUR-2021-30.pdf Licence Creative Commons  Verze souboru 9. 9. 2021

Vlastnosti

Název
LIPIcs-CONCUR-2021-30.pdf
Adresa v ISu
https://repozitar.cz/auth/repo/45606/1139522/
Adresa ze světa
https://repozitar.cz/repo/45606/1139522/
Adresa do Správce
https://repozitar.cz/auth/repo/45606/1139522/?info
Ze světa do Správce
https://repozitar.cz/repo/45606/1139522/?info
Vloženo
Čt 9. 9. 2021 02:00

Práva

Právo číst
  • kdokoliv v Internetu
Právo vkládat
 
Právo spravovat
  • osoba Mgr. Lucie Vařechová, uco 106253
  • osoba RNDr. Daniel Jakubík, uco 139797
  • osoba Mgr. Jolana Surýnková, uco 220973
Atributy
 
Vytisknout
Přidat do schránky Zobrazeno: 29. 3. 2024 02:32