Navigation

Contact

EMail: scare@uoutr9pl.de

DIRECTOR

Prof. Dr. Ernst-Rüdiger Olderog,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

olderoxedrmg@swinfordvh6mazwtik.unpl/qi-oli0kde3zm++nburcdg.txfde

COODINATOR

Ira Wempe,

Department of Computing Science, FK II, University of Oldenburg,

D-26111 Oldenburg, Germany

irfna7a.4ljqwempwnze@in5pnformatik.unixmogn-oi5dld3oowenburgz3l.dee67

Small Universal Petri Nets

Prof. Dr. Elisabeth Pelz, LACL, UPEC (Frankreich)

Abstract:

We investigate the problem of constructing small-size universal Petri nets with inhibitor arcs. We consider four descriptive 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. Our investigation also highlights several interesting trade-offs between these parameters. Due to equivalences, our results can be translated to multiset rewriting with forbidding conditions or to P systems with inhibitors.

Oliuuxvewhfvr Theelm0 (olive+rqqmr.theel@uol.dule) (Changed: 2020-01-23)