Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F21%3A00119747" target="_blank" >RIV/00216224:14330/21:00119747 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1145/3527372.3527374" target="_blank" >https://doi.org/10.1145/3527372.3527374</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3527372.3527374" target="_blank" >10.1145/3527372.3527374</a>

Jazyk výsledku
angličtina
Název v původním jazyce
Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results
Popis výsledku v původním jazyce
We give an overview of recently established results about the effective asymptotic analysis of termination and counter complexity of VASS computations. In contrast to ``classical'' problems such as reachability, boundedness, liveness, coverability, etc., that are EXPSPACE-hard, the decision problems related to VASS asymptotic analysis tend to have low complexity and many important variants are even decidable in polynomial time. We also present selected concepts and techniques used to achieve these results.
Název v anglickém jazyce
Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results
Popis výsledku anglicky
We give an overview of recently established results about the effective asymptotic analysis of termination and counter complexity of VASS computations. In contrast to ``classical'' problems such as reachability, boundedness, liveness, coverability, etc., that are EXPSPACE-hard, the decision problems related to VASS asymptotic analysis tend to have low complexity and many important variants are even decidable in polynomial time. We also present selected concepts and techniques used to achieve these results.

Projekt
<a href="/cs/project/GA21-24711S" target="_blank" >GA21-24711S: Efektivní analýza a optimalizace pravděpodobnostních systémů a her</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění
2021
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Podobné výsledky(10)