论文标题
连续矢量添加系统与状态的可达性几何形状
The Geometry of Reachability in Continuous Vector Addition Systems with States
论文作者
论文摘要
我们研究了与状态（VASS）连续矢量添加系统的可及性集合的几何形状。特别是，我们确定它们几乎是由标记VASS过渡的向量产生的凸锥和凸锥的Minkowski总和。我们使用后者证明，所谓的线性路径方案足以作为固定维度连续vass的可及性的见证人。然后，我们为线性路径方案的可及性问题提供了新的多项式时间算法。最后，我们还确定，用零测试丰富模型使得可及性问题已经对维度二的线性路径方案进行了棘手。
We study the geometry of reachability sets of continuous vector addition systems with states (VASS). In particular we establish that they are almost Minkowski sums of convex cones and zonotopes generated by the vectors labelling the transitions of the VASS. We use the latter to prove that short so-called linear path schemes suffice as witnesses of reachability in continuous VASS of fixed dimension. Then, we give new polynomial-time algorithms for the reachability problem for linear path schemes. Finally, we also establish that enriching the model with zero tests makes the reachability problem intractable already for linear path schemes of dimension two.
