带重置弧的Petri网

Question

如何找到一个与带重置弧的Petri网等价的普通Petri网？这种普通的网必须尊重重置Petri网的语义。

诚挚的问候。

Answer 1

不可能找到一个普通的Petri网，它在任何有意义的意义上都等同于一个带有重置弧的任意Petri网。

众所周知，具有至少一条重置弧的Petri网比普通Petri网具有更强的表达能力。

paper在1977年将Minsky计数自动机(见定理5)归结为带重置弧的Petri网，证明了带重置弧的Petri网的可达性问题是不可判定的。

1981年Ernst Mayr presented an algorithm提出了普通Petri网的可达性问题。

如果可以用算法定义从带重置弧的Petri网到普通Petri网的归约，则两类的可达性问题将具有相同的可判断性状态。这两个结果表明情况并非如此，因此这样的简化是不可能的。

上面引用的论文需要一点技术知识才能阅读，而这些知识通常不是CompSci学生所期望的。对于这个主题的背景知识，我会推荐M.L. Minsky的原始“计算:有限和无限机器”或任何关于计算机科学中的逻辑的现代介绍性文本。