J 2021

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

KUČERA, Antonín

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

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í

Odkazy

Kód RIV

RIV/00216224:14330/21:00119747

Organizační jednotka

Fakulta informatiky

DOI

Klíčová slova anglicky

VASS; termination complexity
Změněno: 27. 4. 2022 09:23, prof. RNDr. Antonín Kučera, Ph.D.

Anotace

V originále

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