Small Universal Deterministic Petri Nets with Inhibitor Arcs
Artiom Alhazov, Sergiu Ivanov, Elisabeth Pelz, Sergey Verlan · HAL (Le Centre pour la Communication Scientifique Directe) · 2016
This paper describes a series of small universal Petri nets with inhibitor arcs. Four parameters of descriptional complexity are considered: the number of places, transitions, inhibitor arcs, and the maximal degree of a transition. A number of techniques for reducing the values of these parameters, with special attention on places, are presented: we describe strongly universal Petri nets with 30, 21, 14, 11, and 5 places, and weakly universal Petri nets with similar parameters. We also show a universal Petri net with 2 inhibitor arcs only. Our investigation highlights several trade-offs. Due to equivalence of the corresponding models, our results can be immediately translated to multiset rewriting with forbidding conditions, to P systems with cooperative rules and inhibitors, or to vector addition systems.