{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T02:59:09Z","timestamp":1780628349371,"version":"3.54.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,1]],"date-time":"2021-10-01T00:00:00Z","timestamp":1633046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3527372.3527374","type":"journal-article","created":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T22:15:05Z","timestamp":1647468905000},"page":"4-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithmic analysis of termination and counter complexity in vector addition systems with states"],"prefix":"10.1145","volume":"8","author":[{"given":"Anton\u00edn","family":"Ku\u010dera","sequence":"first","affiliation":[{"name":"Masaryk University, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,3,16]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Deciding Polynomial Termination Complexity for VASS Programs. In Proceedings of CONCUR 2021 (Leibniz International Proceedings in Informatics), Vol. 203","volume":"30","author":"Ajdar\u00f3w M.","year":"2021","unstructured":"M. Ajdar\u00f3w and A. Ku\u010dera . 2021 . Deciding Polynomial Termination Complexity for VASS Programs. In Proceedings of CONCUR 2021 (Leibniz International Proceedings in Informatics), Vol. 203 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik , 30 : 1 - 30 :15. M. Ajdar\u00f3w and A. Ku\u010dera. 2021. Deciding Polynomial Termination Complexity for VASS Programs. In Proceedings of CONCUR 2021 (Leibniz International Proceedings in Informatics), Vol. 203. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 30:1-30:15.","journal-title":"Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_2_1","first-page":"462","volume-title":"Deciding Fast Termination for Probabilistic VASS with Nondeterminism. In Proceedings of ATVA 2019 (Lecture Notes in Computer Science)","volume":"11781","author":"Br\u00e1zdil T.","unstructured":"T. Br\u00e1zdil , K. Chatterjee , A. Ku\u010dera , P. Novotn\u00fd , and D. Velan . 2019 . Deciding Fast Termination for Probabilistic VASS with Nondeterminism. In Proceedings of ATVA 2019 (Lecture Notes in Computer Science) , Vol. 11781 . Springer , 462 - 478 . T. Br\u00e1zdil, K. Chatterjee, A. Ku\u010dera, P. Novotn\u00fd, and D. Velan. 2019. Deciding Fast Termination for Probabilistic VASS with Nondeterminism. In Proceedings of ATVA 2019 (Lecture Notes in Computer Science), Vol. 11781. Springer, 462-478."},{"key":"e_1_2_1_3_1","first-page":"185","volume-title":"Proceedings of LICS","author":"Br\u00e1zdil T.","year":"2018","unstructured":"T. Br\u00e1zdil , K. Chatterjee , A. Ku\u010dera , P. Novotn\u00fd , D. Velan , and F. Zuleger . 2018. Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS . In Proceedings of LICS 2018 . ACM Press , 185 - 194 . T. Br\u00e1zdil, K. Chatterjee, A. Ku\u010dera, P. Novotn\u00fd, D. Velan, and F. Zuleger. 2018. Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS. In Proceedings of LICS 2018. ACM Press, 185-194."},{"key":"e_1_2_1_4_1","first-page":"478","volume-title":"Proceedings of ICALP","volume":"6199","author":"Br\u00e1zdil T.","year":"2010","unstructured":"T. Br\u00e1zdil , P. Jan\u010dar , and A. Ku\u010dera . 2010. Reachability Games on Extended Vector Addition Systems with States . In Proceedings of ICALP 2010 , Part II (Lecture Notes in Computer Science) , Vol. 6199 . Springer, 478 - 489 . T. Br\u00e1zdil, P. Jan\u010dar, and A. Ku\u010dera. 2010. Reachability Games on Extended Vector Addition Systems with States. In Proceedings of ICALP 2010, Part II (Lecture Notes in Computer Science), Vol. 6199. Springer, 478-489."},{"key":"e_1_2_1_5_1","first-page":"162","volume-title":"Proceedings of CAAP'81 (Lecture Notes in Computer Science)","volume":"112","author":"Broy M.","unstructured":"M. Broy and M. Wirsing . 1981. On the Algebraic Specification of Nondeterministic Programming Languages . In Proceedings of CAAP'81 (Lecture Notes in Computer Science) , Vol. 112 . Springer , 162 - 179 . M. Broy and M. Wirsing. 1981. On the Algebraic Specification of Nondeterministic Programming Languages. In Proceedings of CAAP'81 (Lecture Notes in Computer Science), Vol. 112. Springer, 162-179."},{"key":"e_1_2_1_6_1","first-page":"505","volume-title":"Proceedings of FST&TCS 2010 (Leibniz International Proceedings in Informatics)","volume":"8","author":"Chatterjee K.","year":"2010","unstructured":"K. Chatterjee , L. Doyen , T. Henzinger , and J.-F. Raskin . 2010 . Generalized Mean-payoff and Energy Games . In Proceedings of FST&TCS 2010 (Leibniz International Proceedings in Informatics) , Vol. 8 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik , 505 - 516 . K. Chatterjee, L. Doyen, T. Henzinger, and J.-F. Raskin. 2010. Generalized Mean-payoff and Energy Games. In Proceedings of FST&TCS 2010 (Leibniz International Proceedings in Informatics), Vol. 8. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 505-516."},{"key":"e_1_2_1_7_1","first-page":"24","volume-title":"Proceedings of STOC","author":"Czerwi\u0144ski W.","year":"2019","unstructured":"W. Czerwi\u0144ski , S. Lasota , R. Lazi\u0107 , J. Leroux , and F. Mazowiecki . 2019. The Reachability Problem for Petri Nets Is Not Elementary . In Proceedings of STOC 2019 . ACM Press , 24 - 33 . W. Czerwi\u0144ski, S. Lasota, R. Lazi\u0107, J. Leroux, and F. Mazowiecki. 2019. The Reachability Problem for Petri Nets Is Not Elementary. In Proceedings of STOC 2019. ACM Press, 24-33."},{"key":"e_1_2_1_8_1","first-page":"1","article-title":"Some Classes of Recursive Functions","volume":"4","author":"Grzegorczyk A.","year":"1953","unstructured":"A. Grzegorczyk . 1953 . Some Classes of Recursive Functions . Rozprawy Matematyczne 4 (1953), 1 - 45 . A. Grzegorczyk. 1953. Some Classes of Recursive Functions. Rozprawy Matematyczne 4 (1953), 1-45.","journal-title":"Rozprawy Matematyczne"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90041-0"},{"key":"e_1_2_1_10_1","first-page":"398","volume-title":"Proceedings of STOC'88","author":"Kosaraju S.R.","unstructured":"S.R. Kosaraju and G. Sullivan . 1988. Detecting Cycles in Dynamic Graphs in Polynomial Time . In Proceedings of STOC'88 . ACM Press , 398 - 406 . S.R. Kosaraju and G. Sullivan. 1988. Detecting Cycles in Dynamic Graphs in Polynomial Time. In Proceedings of STOC'88. ACM Press, 398-406."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394751"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics)","volume":"107","author":"Leroux J.","year":"2018","unstructured":"J. Leroux . 2018 . Polynomial Vector Addition Systems With States . In Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics) , Vol. 107 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 134:1-134:13. J. Leroux. 2018. Polynomial Vector Addition Systems With States. In Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics), Vol. 107. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 134:1-134:13."},{"key":"e_1_2_1_13_1","volume-title":"Reachability Problems (Lecture Notes in Computer Science)","author":"Leroux J.","unstructured":"J. Leroux and Ph. Schnoebelen . 2014. On Functions Weakly Computable by Petri Nets and Vector Addition Systems . In Reachability Problems (Lecture Notes in Computer Science) , Vol. 8762 . Springer , 190-202. J. Leroux and Ph. Schnoebelen. 2014. On Functions Weakly Computable by Petri Nets and Vector Addition Systems. In Reachability Problems (Lecture Notes in Computer Science), Vol. 8762. Springer, 190-202."},{"key":"e_1_2_1_14_1","volume-title":"The Reachability Problem Requires Exponential Space. Technical report 62","author":"Lipton R.","unstructured":"R. Lipton . 1976. The Reachability Problem Requires Exponential Space. Technical report 62 . Yale University . R. Lipton. 1976. The Reachability Problem Requires Exponential Space. Technical report 62. Yale University."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322271"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics)","volume":"132","author":"Schmitz S.","year":"2019","unstructured":"S. Schmitz . 2019 . The Parametric Complexity of Lossy Counter Machines . In Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics) , Vol. 132 . Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 129:1-129:15. S. Schmitz. 2019. The Parametric Complexity of Lossy Counter Machines. In Proceedings of ICALP 2018 (Leibniz International Proceedings in Informatics), Vol. 132. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 129:1-129:15."},{"key":"e_1_2_1_17_1","first-page":"745","volume-title":"Proceedings of CAV 2014 (Lecture Notes in Computer Science)","volume":"8559","author":"Sinn M.","unstructured":"M. Sinn , F. Zuleger , and H. Veith . 2013. A Simple and Scalable Static Analysis for Bound Analysis and Amortized Complexity Analysis . In Proceedings of CAV 2014 (Lecture Notes in Computer Science) , Vol. 8559 . Springer , 745 - 761 . M. Sinn, F. Zuleger, and H. Veith. 2013. A Simple and Scalable Static Analysis for Bound Analysis and Amortized Complexity Analysis. In Proceedings of CAV 2014 (Lecture Notes in Computer Science), Vol. 8559. Springer, 745-761."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-016-9402-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45231-5_32"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527372.3527374","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3527372.3527374","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:53Z","timestamp":1750191533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3527372.3527374"}},"subtitle":["a survey of recent results"],"short-title":[],"issued":{"date-parts":[[2021,10]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1145\/3527372.3527374"],"URL":"https:\/\/doi.org\/10.1145\/3527372.3527374","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10]]},"assertion":[{"value":"2022-03-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}