论文标题
坚强的Sleptsov网络完整
Strong Sleptsov Net is Turing-Complete
论文作者
论文摘要
众所周知，一个Sheptsov的网络逐步发射过渡的速度比Petri净打开前景的速度要快，因为它用作同时编程的图形语言。我们根据一般定义及其强大和弱变体提供了基于火率规则的地位转变网的分类。我们介绍并研究了一个强烈的Sheptsov Net，其中一个逐步发射了最大射击的过渡，并证明了它是Turing-Complete的。我们遵循Peterson的证明模式，以证明抑制剂彼得网络正在模拟Shepherdson和Sturgis寄存器机器。我们证明的中心构造是一个强烈的Slectsov网，该网络检查寄存器值（位置标记）是否等于零。
It is known that a Sleptsov net, with multiple firing a transition at a step, runs exponentially faster than a Petri net opening prospects for its application as a graphical language of concurrent programming. We provide classification of place-transition nets based on firability rules considering general definitions and their strong and weak variants. We introduce and study a strong Sleptsov net, where a transition with the maximal firing multiplicity fires at a step, and prove that it is Turing-complete. We follow the proof pattern of Peterson applied to prove that an inhibitor Petri net is Turing-complete simulating a Shepherdson and Sturgis register machine. The central construct of our proof is a strong Sleptsov net that checks whether a register value (place marking) equals zero.
