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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Box-Reachability in Vector Addition Systems

  • Shaull Almagor,
  • Itay Hasson,
  • Michał Pilipczuk,
  • Michael Zaslavski

摘要

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.