Small Universal Petri Nets with Inhibitor Arcs

Abstract

We investigate the problem of construction of small-size universal Petri nets with inhibitor arcs. We consider four descriptional complexity parameters: the number of places, transitions, inhibitor arcs, and the maximal degree of a transition, each of which we try to minimize. We give six constructions having the following values of parameters (listed in the above order): $(30,34,13,3)$, $(14,31,51,8)$, $(11,31,79,11)$, $(21,25,13,5)$, $(67,64,8,3)$, $(58,55,8,5)$ that improve the few known results on this topic. Our investigation also highlights several interesting trade-offs.

References in corpus (1)

• Proceedings Machines, Computations and Universality 2013