论文标题
连续培养皿中的分离器
Separators in Continuous Petri Nets
论文作者
论文摘要
Leroux已证明，培养皿网中的不可收拾，即如果是标记$ \ vec {m} _ \ text {src} $无法达到标记$ \ vec {m} _ \ vec {m} _ \ text {tgt} $，那么就这样的cormula $ qurem arith arth是$φ（\ vec {m} _ \ text {src}）$ holds; $φ$是前向不变的，即$φ（\ vec {m}）$和$ \ vec {m} \ rightArrow \ rightArrow \ vec {m}'$ ins $ nim $φ（\ vec {m}'$）;和$ \negφ（\ vec {m} _ \ text {tgt}）$保持。尽管这些分离器可以用作解释和正式的无法达到的不可行证明，但由于其最差的案例尺寸，至少是Ackermannian，并且检查公式是否是一个分离器，至少是指数级（在配方群尺寸）。 我们表明，在连续的培养皿网中，可以克服这两个问题。我们介绍了本地封闭的分离器，并证明：（a）可以在多项式时间内计算的本地闭合分离器见证了无法达到的性能； （b）检查公式是否是本地封闭的分隔符，在NC中（因此，比不可碰到的简单，是P-Complete）。 我们进一步考虑了（存在）设定的可达性的更一般的问题，其中将两组标记作为凸多台面。我们表明，尽管我们的方法无法直接扩展，但我们可以通过更改的Petri网络有效地证明无法达到无法达到的能力。
Leroux has proved that unreachability in Petri nets can be witnessed by a Presburger separator, i.e. if a marking $\vec{m}_\text{src}$ cannot reach a marking $\vec{m}_\text{tgt}$, then there is a formula $φ$ of Presburger arithmetic such that: $φ(\vec{m}_\text{src})$ holds; $φ$ is forward invariant, i.e., $φ(\vec{m})$ and $\vec{m} \rightarrow \vec{m}'$ imply $φ(\vec{m}'$); and $\neg φ(\vec{m}_\text{tgt})$ holds. While these separators could be used as explanations and as formal certificates of unreachability, this has not yet been the case due to their worst-case size, which is at least Ackermannian, and the complexity of checking that a formula is a separator, which is at least exponential (in the formula size). We show that, in continuous Petri nets, these two problems can be overcome. We introduce locally closed separators, and prove that: (a) unreachability can be witnessed by a locally closed separator computable in polynomial time; (b) checking whether a formula is a locally closed separator is in NC (so, simpler than unreachability, which is P-complete). We further consider the more general problem of (existential) set-to-set reachability, where two sets of markings are given as convex polytopes. We show that, while our approach does not extend directly, we can efficiently certify unreachability via an altered Petri net.
