| 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, vol. 8, No 4, p. 4-21. ISSN 2372-3491. Available from: https://dx.doi.org/10.1145/3527372.3527374. |
Other formats:
BibTeX
LaTeX
RIS
@article{1849418,
author = {Kučera, Antonín},
article_location = {New York, NY, United States},
article_number = {4},
doi = {http://dx.doi.org/10.1145/3527372.3527374},
keywords = {VASS; termination complexity},
language = {eng},
issn = {2372-3491},
journal = {ACM SIGLOG News},
title = {Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results},
url = {https://doi.org/10.1145/3527372.3527374},
volume = {8},
year = {2021}
}
TY - JOUR
ID - 1849418
AU - Kučera, Antonín
PY - 2021
TI - Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results
JF - ACM SIGLOG News
VL - 8
IS - 4
SP - 4-21
EP - 4-21
PB - Association for Computing Machinery
SN - 23723491
KW - VASS
KW - termination complexity
UR - https://doi.org/10.1145/3527372.3527374
N2 - 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.
ER -
KUČERA, Antonín. Algorithmic Analysis of Termination and Counter Complexity in Vector Addition Systems with States: A Survey of Recent Results. \textit{ACM SIGLOG News}. New York, NY, United States: Association for Computing Machinery, 2021, vol.~8, No~4, p.~4-21. ISSN~2372-3491. Available from: https://dx.doi.org/10.1145/3527372.3527374.
|
