The polynomial complexity of vector addition systems with states

DOI10.1007/978-3-030-45231-5_32MaRDI QIDQ2200853zbMATH OpenOpenAlexFDO

Authors Florian Zuleger

Publication date 23 September 2020

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1907.01076

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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 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 $Theta(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 $1lekle{2}^n$, where $n$ is the dimension of the considered vector addition system.

Recommendations

• Polynomial vector addition systems with states
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• A multiparameter analysis of the boundedness problem for vector addition systems
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• When reachability meets Grzegorczyk

Cites work

• scientific article; zbMATH DE number 827979 (Why is no real title available?)
• A Language-Based Comparison of Extensions of Petri Nets with and without Whole-Place Operations
• Complexity and resource bound analysis of imperative programs using difference constraints
• Decidability of parameterized verification
• Efficient Algorithms for Asymptotic Bounds on Termination Time in VASS
• Liveness of parameterized timed networks
• On the Expressive Power of Communication Primitives in Parameterised Systems
• On the \(\omega\)-language expressive power of extended Petri nets
• On the reachability problem for 5-dimensional vector addition systems
• Parallel program schemata
• Polynomial vector addition systems with states
• Reasoning about systems with many processes
• The covering and boundedness problems for vector addition systems
• The polynomial complexity of vector addition systems with states
• Tutorial on parameterized model checking of fault-tolerant distributed algorithms

Cited in

(6)

• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• The polynomial complexity of vector addition systems with states
• Hyper-Ackermannian bounds for pushdown vector addition systems
• scientific article; zbMATH DE number 7407775 (Why is no real title available?)
• Type-based analysis of logarithmic amortised complexity
• Polynomial vector addition systems with states

This page was built for publication: The polynomial complexity of vector addition systems with states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2200853)