Sleptsov nets are Turing-complete

DOI10.1016/J.TCS.2023.114346arXiv2306.12440MaRDI QIDQ6138839FDOQ6138839

Authors: Bernard Berthomieu, Dmitry A. Zaitsev 

Publication date: 16 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: The present paper proves that a Sleptsov net (SN) is Turing-complete, that considerably improves, with a brief construct, the previous result that a strong SN is Turing-complete. Remind that, unlike Petri nets, an SN always fires enabled transitions at their maximal firing multiplicity, as a single step, leaving for a nondeterministic choice of which fireable transitions to fire. A strong SN restricts nondeterministic choice to firing only the transitions having the highest firing multiplicity.

Full work available at URL: https://arxiv.org/abs/2306.12440

zbMATH Keywords

Turing-completenessmultiple firingplace-transition netsleptsov net

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Computability of Recursive Functions
• The tool TINA – Construction of abstract state spaces for petri nets and time petri nets

Cited In (1)

• GPU based virtual machine for Sleptsov net computing

This page was built for publication: Sleptsov nets are Turing-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6138839)