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

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KUČERA Antonín

Year of publication 2021
Type Article in Periodical
Magazine / Source ACM SIGLOG News
MU Faculty or unit

Faculty of Informatics

Citation
Web ACM Digital Library
Doi http://dx.doi.org/10.1145/3527372.3527374
Keywords VASS; termination complexity
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info