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

KUČERA, Antonín. Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results. ACM SIGLOG News. New York, NY, United States: Association for Computing Machinery, 2021, roč. 8, č. 4, s. 4-21. ISSN 2372-3491. Dostupné z: https://dx.doi.org/10.1145/3527372.3527374.

Základní údaje

• Originální název: Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results
• Autoři: KUČERA, Antonín (203 Česká republika, garant, domácí).
• Vydání: ACM SIGLOG News, New York, NY, United States, Association for Computing Machinery, 2021, 2372-3491.

Další údaje

• Originální jazyk: angličtina
• Typ výsledku: Článek v odborném periodiku
• Obor: 10200 1.2 Computer and information sciences
• Stát vydavatele: Spojené státy
• Utajení: není předmětem státního či obchodního tajemství
• WWW: ACM Digital Library
• Kód RIV: RIV/00216224:14330/21:00119747
• Organizační jednotka: Fakulta informatiky
• Doi: http://dx.doi.org/10.1145/3527372.3527374
• Klíčová slova anglicky: VASS; termination complexity

Anotace

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ávaznosti

• GA21-24711S, projekt VaV: Název: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Akronym: Efektivní analýza a optimalizace pravděpodobnostní)

Investor: Grantová agentura ČR, Efektivní analýza a optimalizace pravděpodobnostních systémů a her