Efficient Analysis of VASS Termination Complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F20%3A00114250" target="_blank" >RIV/00216224:14330/20:00114250 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/3373718.3394751" target="_blank" >http://dx.doi.org/10.1145/3373718.3394751</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3373718.3394751" target="_blank" >10.1145/3373718.3394751</a>
Alternative languages
Result language
angličtina
Original language name
Efficient Analysis of VASS Termination Complexity
Original language description
The termination complexity of a given VASS is a function $L$ assigning to every $n$ the length of the longest nonterminating computation initiated in a configuration with all counters bounded by $n$. We show that for every VASS with demonic nondeterminism and every fixed $k$, the problem whether $L in G_k$, where $G_k$ is the $k$-th level in the Grzegorczyk hierarchy, is decidable in polynomial time. Furthermore, we show that if $L notin G_k$, then L grows at least as fast as the generator $F_k+1$ of $G_k+1$. Hence, for every terminating VASS, the growth of $L$ can be reasonably characterized by the least $k$ such that $L in G_k$. Furthermore, we consider VASS with both angelic and demonic nondeterminism, i.e., VASS games where the players aim at lowering/raising the termination time. We prove that for every fixed $k$, the problem whether $L in G_k$ for a given VASS game is NP-complete. Furthermore, if $L notin G_k$, then $L$ grows at least as fast as $F_k+1$.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10200 - Computer and information sciences
Result continuities
Project
<a href="/en/project/GA18-11193S" target="_blank" >GA18-11193S: Algorithms for Infinite-State Discrete Systems and Games</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science
ISBN
9781450371049
ISSN
—
e-ISSN
—
Number of pages
13
Pages from-to
676-688
Publisher name
ACM
Place of publication
New York, USA
Event location
Saarbrucken, Germany
Event date
Jan 1, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000665014900052