Strong sleptsov nets are Turing complete
From MaRDI portal
Publication:6132054
DOI10.1016/J.INS.2022.11.098arXiv2201.09034MaRDI QIDQ6132054FDOQ6132054
Authors: Dmitry A. Zaitsev 
Publication date: 18 April 2024
Published in: Information Sciences (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/2201.09034
Cited In (1)
This page was built for publication: Strong sleptsov nets are Turing complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6132054)
