如何找到一个普通的Petri网等价于带有复位弧的Petri网？这个普通的网络必须尊重重置 Petri 网络的语义。
此致。
问问题
650 次
1 回答
2
不可能找到一个普通的 Petri 网，它在任何有意义的意义上都等同于具有复位弧的任意 Petri 网。
众所周知，具有至少一个复位弧的 Petri 网类比普通 Petri 网更严格地表达。
在他们 1977 年的论文Toshiro Araki 和 Tadao Kasami 通过将 Minsky 计数器自动机（见定理 5）简化为具有复位弧的 Petri 网证明了具有复位弧的 Petri 网的可达性问题是不可判定的。
而在 1981 年 Ernst Mayr提出了一种用于普通 Petri 网可达性问题的算法。
如果可以通过算法定义从具有重置弧的 Petri 网到普通 Petri 网的归约，则两个类的可达性问题将具有相同的可判定性状态。这两个结果表明情况并非如此，因此这种减少是不可能的。
上面引用的论文需要一些技术知识才能阅读，这通常不是 CompSci 学生所期望的。对于这个主题的背景，我建议使用 ML Minsky 的原始“计算：有限和无限机器”或任何关于计算机科学逻辑的现代介绍性文本。
于 2015-02-21T13:26:12.633 回答