Integer vector addition systems with states

DOI10.1007/978-3-319-11439-2_9MaRDI QIDQ3447699zbMATH OpenOpenAlexFDO

Authors Christoph Haase, Simon Halfon

Publication date 28 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: This paper studies reachability, coverability and inclusion problems for Integer Vector Addition Systems with States (ZVASS) and extensions and restrictions thereof. A ZVASS comprises a finite-state controller with a finite number of counters ranging over the integers. Although it is folklore that reachability in ZVASS is NP-complete, it turns out that despite their naturalness, from a complexity point of view this class has received little attention in the literature. We fill this gap by providing an in-depth analysis of the computational complexity of the aforementioned decision problems. Most interestingly, it turns out that while the addition of reset operations to ordinary VASS leads to undecidability and Ackermann-hardness of reachability and coverability, respectively, they can be added to ZVASS while retaining NP-completness of both coverability and reachability.

Recommendations

• Affine extensions of integer vector addition systems with states
• The complexity of reachability in affine vector addition systems with states
• Reachability in two-dimensional vector addition systems with states is PSPACE-complete
• Polynomial vector addition systems with states
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states

Cited in

(34)

• On decidability and complexity of low-dimensional robot games
• Reachability problems in low-dimensional nondeterministic polynomial maps over integers
• Coverability Is undecidable in one-dimensional pushdown vector addition systems with resets
• Taming past LTL and flat counter systems
• Context-free commutative grammars with integer counters and resets
• Recent advances on reachability problems for valence systems (invited talk)
• On robot games of degree two
• Purely Catalytic P Systems over Integers and Their Generative Power
• Mixing coverability and reachability to analyze VASS with one zero-test
• Costs and rewards in priced timed automata
• Affine extensions of integer vector addition systems with states
• On Affine Reachability Problems
• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• The complexity of reachability in affine vector addition systems with states
• Affine extensions of integer vector addition systems with states
• scientific article; zbMATH DE number 7407775 (Why is no real title available?)
• Automata for unordered trees
• Long-Run Average Behavior of Vector Addition Systems with States
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• Unboundedness problems for machines with reversal-bounded counters
• Reasoning about reversal-bounded counter machines
• The boundedness and zero isolation problems for weighted automata over nonnegative rationals
• The complexity of soundness in workflow nets
• The complexity of bidirected reachability in valence systems
• Infinite precedence graphs for consistency verification in P-time event graphs
• On the size of finite rational matrix semigroups
• Non-global Parikh tree automata
• Monus semantics in vector addition systems with states
• Soundness of reset workflow nets
• The geometry of reachability in continuous vector addition systems with states
• Challenges of the reachability problem in infinite-state systems (invited paper)
• Boundedness of cost register automata over the integer min-plus semiring
• The complexity of separability for semilinear sets and Parikh automata
• Algebraic program analysis

This page was built for publication: Integer vector addition systems with states

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