Sleptsov Nets are Turing-complete

June 17, 2023 · The Ethereal · 🏛 Theoretical Computer Science

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Bernard Berthomieu, Dmitry A. Zaitsev arXiv ID 2306.12440 Category cs.CC: Computational Complexity Cross-listed cs.DC Citations 4 Venue Theoretical Computer Science Last Checked 2 months ago
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.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Computational Complexity