Abstract
Vector addition systems are an important model in theoretical computer science and have been used in a variety of areas. In this paper, we consider vector addition systems with states over a parameterized initial configuration. For these systems, we are interested in the standard notion of computational time complexity, i.e., we want to understand the length of the longest trace for a fixed vector addition system with states depending on the size of the initial configuration. We show that the asymptotic complexity of a given vector addition system with states is either \(\varTheta (N^k)\) for some computable integer k, where N is the size of the initial configuration, or at least exponential. We further show that k can be computed in polynomial time in the size of the considered vector addition system. Finally, we show that \(1 \le k \le 2^n\), where n is the dimension of the considered vector addition system.
Chapter PDF
Similar content being viewed by others
References
Parosh Aziz Abdulla, Giorgio Delzanno, and Laurent van Begin. A language-based comparison of extensions of Petri nets with and without whole-place operations. In LATA, pages 71–82, 2009.
Benjamin Aminof, Sasha Rubin, and Florian Zuleger. On the expressive power of communication primitives in parameterised systems. In LPAR, pages 313–328, 2015.
Benjamin Aminof, Sasha Rubin, Florian Zuleger, and Francesco Spegni. Liveness of parameterized timed networks. In ICALP, pages 375–387, 2015.
Roderick Bloem, Swen Jacobs, Ayrat Khalimov, Igor Konnov, Sasha Rubin, Helmut Veith, and Josef Widder. Decidability in parameterized verification. SIGACT News, 47(2):53–64, 2016.
Tomás Brázdil, Krishnendu Chatterjee, AntonÃn Kucera, Petr Novotný, Dominik Velan, and Florian Zuleger. Efficient algorithms for asymptotic bounds on termination time in VASS. In LICS, pages 185–194, 2018.
Leonard Dickson. Finiteness of the odd perfect and primitive abundant numbers with \(n\) distinct prime factors. Am. J. Math, 35:413–422, 1913.
Javier Esparza and Mogens Nielsen. Decidability issues for Petri nets - a survey. Elektronische Informationsverarbeitung und Kybernetik, 30(3):143–160, 1994.
Alain Finkel, Gilles Geeraerts, Jean-François Raskin, and Laurent van Begin. On the omega-language expressive power of extended Petri nets. TCS, 356(3):374–386, 2006.
Steven M. German and A. Prasad Sistla. Reasoning about systems with many processes. J. ACM, 39(3), 675–735, 1992.
John E. Hopcroft and Jean-Jacques Pansiot. On the reachability problem for 5-dimensional vector addition systems. TCS, 8:135–159, 1979.
Annu John, Igor Konnov, Ulrich Schmid, Helmut Veith, and Josef Widder. Parameterized model checking of fault-tolerant distributed algorithms by abstraction. In FMCAD, pages 201–209, 2013.
Alexander Kaiser, Daniel Kroening, and Thomas Wahl. A widening approach to multithreaded program verification. TOPLAS, 36(4):14:1–14:29, 2014.
Richard M. Karp and Raymond E. Miller. Parallel program schemata. J. Comput. Syst. Sci., 3(2):147–195, 1969.
S. Rao Kosaraju and Gregory F. Sullivan. Detecting cycles in dynamic graphs in polynomial time (preliminary version). In STOC, pages 398–406, 1988.
Jérôme Leroux. Polynomial vector addition systems with states. In ICALP, pages 134:1–134:13, 2018.
Richard J. Lipton. The Reachability Problem Requires Exponential space. Research report 62. Department of Computer Science, Yale University, 1976.
Charles Rackoff. The covering and boundedness problems for vector addition systems. TCS, 6:223–231, 1978.
Moritz Sinn, Florian Zuleger, and Helmut Veith. A simple and scalable static analysis for bound analysis and amortized complexity analysis. In CAV, pages 745–761, 2014.
Moritz Sinn, Florian Zuleger, and Helmut Veith. Difference constraints: An adequate abstraction for complexity analysis of imperative programs. In FMCAD, pages 144–151, 2015.
Moritz Sinn, Florian Zuleger, and Helmut Veith. Complexity and resource bound analysis of imperative programs using difference constraints. JAR, 59:3–45, 2017.
Florian Zuleger. The polynomial complexity of vector addition systems with states. CoRR, abs/1907.01076, 2019.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Zuleger, F. (2020). The Polynomial Complexity of Vector Addition Systems with States. In: Goubault-Larrecq, J., König, B. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2020. Lecture Notes in Computer Science(), vol 12077. Springer, Cham. https://doi.org/10.1007/978-3-030-45231-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-030-45231-5_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45230-8
Online ISBN: 978-3-030-45231-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)