May, 2024

Petri 网中的双可达性

TL;DR我们研究了带有数据的 Petri 网,Petri 网的扩展,其中令牌携带来自无限数据域的值,并且过渡的可执行性取决于数据值之间的等式。我们提供了一个双向可达性问题的决策过程:给定一个 Petri 网及其两个配置,我们询问每个配置是否可以从另一个配置达到。这推动了可判定性边界,因为双向可达性问题包含可覆盖性问题(已知可判定)并被可达性问题所包含(其可判定性状态未知)。