A Small Universal Petri Net
This work provides a minimal universal Petri net for theoretical computer science, addressing the problem of computational universality in formal models, but it is incremental as it builds on existing Turing machine simulations.
The authors constructed a universal deterministic inhibitor Petri net with 14 places, 29 transitions, and 138 arcs by simulating a weakly universal Turing machine with 2 states and 4 symbols, achieving exponential time complexity relative to the Turing machine's runtime.
A universal deterministic inhibitor Petri net with 14 places, 29 transitions and 138 arcs was constructed via simulation of Neary and Woods' weakly universal Turing machine with 2 states and 4 symbols; the total time complexity is exponential in the running time of their weak machine. To simulate the blank words of the weakly universal Turing machine, a couple of dedicated transitions insert their codes when reaching edges of the working zone. To complete a chain of a given Petri net encoding to be executed by the universal Petri net, a translation of a bi-tag system into a Turing machine was constructed. The constructed Petri net is universal in the standard sense; a weaker form of universality for Petri nets was not introduced in this work.