conference paper published yes Tomáš Brázdil author Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Antonín Kučera author Petr Novotny author 3CC3B868-F248-11E8-B48F-1D18A9856A87 Dominik Velan author Florian Zuleger author KrCh department LICS: Logic in Computer Science Efficient Algorithms for Computer Aided Verification project Quantitative Graph Games: Theory and Applications project Rigorous Systems Engineering project Vector Addition Systems with States (VASS) provide a well-known and fundamental model for the analysis of concurrent processes, parameterized systems, and are also used as abstract models of programs in resource bound analysis. In this paper we study the problem of obtaining asymptotic bounds on the termination time of a given VASS. In particular, we focus on the practically important case of obtaining polynomial bounds on termination time. Our main contributions are as follows: First, we present a polynomial-time algorithm for deciding whether a given VASS has a linear asymptotic complexity. We also show that if the complexity of a VASS is not linear, it is at least quadratic. Second, we classify VASS according to quantitative properties of their cycles. We show that certain singularities in these properties are the key reason for non-polynomial asymptotic complexity of VASS. In absence of singularities, we show that the asymptotic complexity is always polynomial and of the form Θ(nk), for some integer k d, where d is the dimension of the VASS. We present a polynomial-time algorithm computing the optimal k. For general VASS, the same algorithm, which is based on a complete technique for the construction of ranking functions in VASS, produces a valid lower bound, i.e., a k such that the termination complexity is (nk). Our results are based on new insights into the geometry of VASS dynamics, which hold the potential for further applicability to VASS analysis. IEEE2018Oxford, United Kingdom eng 978-1-4503-5583-4 1804.10985 00054526280002010.1145/3209108.3209191 F138033185 - 194 Brázdil, T., Chatterjee, K., Kučera, A., Novotný, P., Velan, D., &#38; Zuleger, F. (2018). Efficient algorithms for asymptotic bounds on termination time in VASS (Vol. F138033, pp. 185–194). Presented at the LICS: Logic in Computer Science, Oxford, United Kingdom: IEEE. <a href="https://doi.org/10.1145/3209108.3209191">https://doi.org/10.1145/3209108.3209191</a> Brázdil T, Chatterjee K, Kučera A, Novotný P, Velan D, Zuleger F. Efficient algorithms for asymptotic bounds on termination time in VASS. In: Vol F138033. IEEE; 2018:185-194. doi:<a href="https://doi.org/10.1145/3209108.3209191">10.1145/3209108.3209191</a> Brázdil T, Chatterjee K, Kučera A, Novotný P, Velan D, Zuleger F. 2018. Efficient algorithms for asymptotic bounds on termination time in VASS. LICS: Logic in Computer Science, ACM/IEEE Symposium on Logic in Computer Science, vol. F138033, 185–194. T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, and F. Zuleger, “Efficient algorithms for asymptotic bounds on termination time in VASS,” presented at the LICS: Logic in Computer Science, Oxford, United Kingdom, 2018, vol. F138033, pp. 185–194. Brázdil, Tomáš, et al. <i>Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS</i>. Vol. F138033, IEEE, 2018, pp. 185–94, doi:<a href="https://doi.org/10.1145/3209108.3209191">10.1145/3209108.3209191</a>. T. Brázdil, K. Chatterjee, A. Kučera, P. Novotný, D. Velan, F. Zuleger, in:, IEEE, 2018, pp. 185–194. Brázdil, Tomáš, Krishnendu Chatterjee, Antonín Kučera, Petr Novotný, Dominik Velan, and Florian Zuleger. “Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS,” F138033:185–94. IEEE, 2018. <a href="https://doi.org/10.1145/3209108.3209191">https://doi.org/10.1145/3209108.3209191</a>. 1432018-12-11T11:44:51Z2025-06-04T08:04:55Z