Box-Reachability in Vector Addition Systems

Shaull Almagor, Itay Hasson, Michał Pilipczuk, Michael Zaslavski · 2025

Read Box-Reachability in Vector Addition Systems by Shaull Almagor, Itay Hasson, Michał Pilipczuk, Michael Zaslavski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-12853.txt.

Introduction

Shaull Almagor and co-authors study in 2025 a new form of reachability in vector addition systems, a model used in computer science. In the standard form, a path must stay in the positive range. In their box form, the path must also stay below the target vector, inside the box set by zero and that target.

Their main result says that for two dimensional systems, the box reachable set almost matches the standard set. The two agree for all vectors whose parts are both above some threshold. The authors also compare the two forms more broadly. Their proof uses tools from convex geometry, which may interest readers in formal methods.

Catalog record

CREATORShaull Almagor, Itay Hasson, Michał Pilipczuk, Michael Zaslavski
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-12853

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Box-Reachability in Vector Addition Systems Shaull Almagor, Itay Hasson, Michał Pilipczuk, Michael Zaslavski Abstract We consider a variant of reachability in Vector Addition Systems (VAS) dubbed box reachability , whereby a vector 𝒗 ∈ ℕ d \boldsymbol{v}\in\mathbb{N}^{d} is box-reachable from 𝟎 \boldsymbol{0} in a VAS 𝒱 \mathcal{V} if 𝒱 \mathcal{V} admits a path from 𝟎 \boldsymbol{0} to 𝒗 \boldsymbol{v} that not only stays in the positive orthant (as in the standard VAS semantics), but also stays below 𝒗 \boldsymbol{v} , i.e., within the “box” whose opposite corners are 𝟎 \boldsymbol{0} and 𝒗 \boldsymbol{v} . Our main result is that for two-dimensional VAS, the set of box-reachable vertices almost coincides with the standard reachability set: the two sets coincide for all vectors whose coordinates are both above some threshold W W . We also study properties of box-reachability, exploring the differences and similarities with standard reachability. Technically, our main result is proved using powerful machinery from convex geometry. 1 Introduction Vector Addition Systems (VAS) are a well-established formalism for modelling and reasoning about concurrent systems, hardware and software analysis, biological and chemical processes, and many more. In particular, VAS and Petri-Nets are equivalent (in a sense), with the latter being a long-studied model [ 17 ] . Formally, a VAS is given by a finite set of vectors \mathcal{V}\subseteq\mathbb{Z}^{d} . A trace in \mathcal{V} is then a sequence of vectors obtained by summing vectors from \mathcal{V} , provided that all coordinates remain non-negative. The latter requirement is dubbed the VAS Semantics . A vector \boldsymbol{v} is reachable if there is a trace that starts 1 1 1 Often a starting vector is also given, but the problem has the same “flavour” also when starting from \boldsymbol{0} . at \boldsymbol{0} and ends in \boldsymbol{v} . The fundamental problem for VAS is reachability : given a vector \boldsymbol{v} , decide whether it is reachable in \mathcal{V} . This problem has a rich history, and its exact complexity has been only recently settled as ACKERMANN-Complete [ 6 , 13 ] , with better bounds known for dimensions 1 and 2 . A more involved problem is characterizing the set of reachable vectors. In general, there is no simple characterization (which is understandable, given the high complexity of reachability). However, in dimension up to five this set is semilinear [ 10 ] . From a modelling perspective, the coordinates of the vectors in a VAS typically correspond to some resources (e.g., memory locks, battery level, queue size, molecule concentration, etc.). Then, reachability amounts to the question of whether a certain configuration of the resources can be reached. In the standard reachability question, no attention is paid to how the target configuration is reached. In particular, it may be the case that in order to reach a certain target configuration, the trace must go through configurations with a higher number of certain resources than the target. Such traces may be less useful to the designer, or might not fit with their intent. For example, consider a chemical solution of three chemical compounds A,B,C , whose respective quantities are modelled as (x_{A},x_{B},x_{C}) . Suppose we start at (1,2,2) and wish to reach (10,10,10) . It may be the case that due to reactions between the materials, one first needs to flood the solution with compound A (going above 10 ), and only then the reactions can lead down to (10,10,10) . In case A is expensive, dangerous or volatile, this trace might not be useful for actual reachability. Similar settings can occur with any types of resources, where one does not want to go over the amount of the resources in the target before reaching it. To capture this notion, we introduce box-reachability : a vector \boldsymbol{x}=(x_{1},\ldots,x_{d})\in\mathbb{N}^{d} is box-reachable in a VAS \mathcal{V} if there is a trace from \boldsymbol{0} to \boldsymbol{x} such that throughout the entire trace, each coordinate i remains at most x_{i} . Example 1 Consider a 2 -VAS \mathcal{V}=\{(-1,2),(2,-1),(10,10)\} . Let us examine the configurations \boldsymbol{t_{1}}=(11,11) and \boldsymbol{t_{2}}=(21,21) . Observe that (-1,2)+(2,-1)=(1,1) , and the path (-1,2),(2,-1) can be taken from every vector (x,y)\geq(1,0) . Thus, both \boldsymbol{t_{1}} and \boldsymbol{t_{2}} are reachable in \mathcal{V} , via the paths \pi_{1}:\boldsymbol{0}\xrightarrow{(10,10)(-1,2)(2,-1)}_{\mathbb{N}}{(11,11)} and \pi_{2}:\boldsymbol{0}\xrightarrow{(10,10)((-1,2)(2,-1))^{11}}_{\mathbb{N}}{(21,21)} , respectively. However, both \pi_{1} and \pi_{2} exceed their respective boxes. Indeed, the penultimate vector reached by \pi_{1} is (9,12) (exceeding (11,11) ), and by \pi_{2} is (19,22) (exceeding (21,21) ). It is not hard to see that \boldsymbol{t_{1}}\notin\mathsf{BoxReach}(\mathcal{V}) . Indeed, the first vector that must be taken in any path in \mathcal{V} is (10,10) , and from there any added vector in \mathcal{V} exceeds the (11,11) box. However, \boldsymbol{t_{2}}\in\mathsf{BoxReach}(\mathcal{V}) , via the run \pi_{3}:\boldsymbol{0}\xrightarrow{(10,10)(-1,2)(2,-1)(10,10)}_{\mathbb{N}}{(21,21)} . Moreover, a similar path can be taken to box-reach any vector (k,k) with k\geq 20 , via the path \boldsymbol{0}\xrightarrow{(10,10)((-1,2)(2,-1))^{k-20}(10,10)}_{\mathbb{N}}{(k,k)} . This example illustrates two central characteristics of the box-reachable set. First, we notice that the classical reachability set does not coincide with box-reachability. Indeed, as we show above, (11,11) is reachable but not box-reachable. An even more obvious example of this is that (30,0) is reachable in \mathcal{V} (via the path (10,10)(2,-1)^{10} ), but is not box-reachable, since all paths start in (10,10) and in particular go above 0 in the {\mathsf{y}} -coordinate. The second characteristic is that vectors that are “deep” enough in the positive quadrant, e.g., (21,21) , allow us enough wiggle room along the path to apply all the “unsafe” vectors that exceed their box (e.g., (-1,2),(2,-1) ) without leaving the overall box. This suggests that perhaps the box-reachability set and the classical reachability set do coincide for vectors with large-enough entries. Indeed, this is the main contribution of this paper, for dimension 2. ∎ Contribution. We focus on dimension 2 (see Examples 2 and 2 for context on this). In Theorem 3.1 we characterize the box-reachable set as follows: for every 2\mbox{\rm-VAS} there exists a (polynomial size) W\in\mathbb{N} such that the reachability set and the box-reachability sets coincide on [W,\infty)^{2} . Technically, the proof of Theorem 3.1 uses insights on the geometry of the reachable set in the context of the cone it spans. We rely on nontrivial machinery from convex geometry (specifically, Steinitz’s lemma [ 8 ] and the Deep-in-the-cone Lemma [ 5 ] ; both are introduced in Section 4.1 ). Focusing on 2\mbox{\rm-VAS} may seem limited. To justify this, we show that our result no longer holds neither for 3\mbox{\rm-VAS} nor for 1\mbox{\rm-VASS} (i.e., Vector Addition Systems with States). In addition, we study the shape of the box-reachable set, showing that it is semilinear for 2\mbox{\rm-VAS} as well as 1\mbox{\rm-VASS} , and drawing a connection between box reachability in d\mbox{\rm-VAS} and standard reachability in 2d\mbox{\rm-VAS} . In a broader context, our work can be viewed as a form of boundedness constraint on the VAS, in the sense that box-reaching runs are bounded by their target. Unlike boundedness by a constant, this still allows counters to become arbitrarily large. In terms of understanding the geometry of VAS, our contribution stands in an interesting contrast to standard methods of reasoning about VAS: the most common approach in reasoning about low-dimensional VAS (and VASS) is that of Linear Path Schemes, which intuitively allow to iterate a small number of cycles many

Read the complete text