A Small Universal Petri Net

Dmitry A. Zaitsev
(International Humanitarian University, Professor)

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.

In Turlough Neary and Matthew Cook: Proceedings Machines, Computations and Universality 2013 (MCU 2013), Zürich, Switzerland, 9/09/2013 - 11/09/2013, Electronic Proceedings in Theoretical Computer Science 128, pp. 190–202.
the smallest known universal Petri net
Published: 4th September 2013.

ArXived at: http://dx.doi.org/10.4204/EPTCS.128.22 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org