J 2021

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

KUČERA, Antonín

Basic information

Original name

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

Authors

KUČERA, Antonín (203 Czech Republic, guarantor, belonging to the institution)

Edition

ACM SIGLOG News, New York, NY, United States, Association for Computing Machinery, 2021, 2372-3491

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10200 1.2 Computer and information sciences

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

RIV identification code

RIV/00216224:14330/21:00119747

Organization unit

Faculty of Informatics

DOI

Keywords in English

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

Abstract

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.

Links

GA21-24711S, research and development project
Name: Efektivní analýza a optimalizace pravděpodobnostních systémů a her (Acronym: Efektivní analýza a optimalizace pravděpodobnostní)
Investor: Czech Science Foundation