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

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

KUČERA Antonín

Rok publikování 2021
Druh Článek v odborném periodiku
Časopis / Zdroj ACM SIGLOG News
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www ACM Digital Library
Doi http://dx.doi.org/10.1145/3527372.3527374
Klíčová slova VASS; termination complexity
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.