Registered: Mar 2013
Posts: 1

In 1974 Tilak Agervala showed that Inhibitor Petri net is Turing-complete:

T. Agerwala, A complete model for representing the coordination of asynchronous processes, John Hopkins Univ., Hopkins Comput. Sci. Prog., Baltimore, MD, Res. Rep. No. 32, Jul. 1974.

In 2010 Dmitry Zaitsev constructed Universal Petri Net in an explicit form; it consists of a few thousands nodes as estimated in:

Zaitsev D.A. Universal Petri net, Cybernetics and Systems Analysis, Volume 48, Number 4 (2012), 498-511, DOI: 10.1007/s10559-012-9429-4

Recently, Universal Petri net with 14 places and 42 transitions was constructed by Dmitry Zaitsev:

Zaitsev D.A. Toward the Minimal Universal Petri Net, IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2013, 1- 12, DOI: 10.1109/TSMC.2012.2237549

Thus, a contest for minimal universal Petri net was unleashed.

Petri net paradigm of computation demands minimality of size for hardware and software implementation as well as minimal time/space complexity of running.

__________________
daze.ho.ua

Report this post to a moderator | IP: Logged