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. |
Další formáty:
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, roč.~8, č.~4, s.~4-21. ISSN~2372-3491. Dostupné z: https://dx.doi.org/10.1145/3527372.3527374.
|