The polynomial complexity of vector addition systems with states

DOI10.1007/978-3-030-45231-5_32zbMATH Open1442.68154arXiv1907.01076OpenAlexW3022740807MaRDI QIDQ2200853FDOQ2200853

Authors: Florian Zuleger 

Publication date: 23 September 2020

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.

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

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

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)

Cites Work

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

Cited In (6)

• ATLAS: automated amortised complexity analysis of self-adjusting data structures
• The polynomial complexity of vector addition systems with states
• Title not available (Why is that?)
• Hyper-Ackermannian bounds for pushdown vector addition systems
• Polynomial vector addition systems with states
• Type-based analysis of logarithmic amortised complexity

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)