Box-Reachability in Vector Addition Systems
摘要
We consider a variant of reachability in Vector Addition Systems (VAS) dubbed box reachability, whereby a vector \(\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. 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.