ICE-TCS Lectures Series - David de Frutos Escrig - (Un)decidability in Petri nets with name creation and replication

The next ICE-TCS  talk for this semester will be delivered on Monday, 28 June, by David de Frutos Escrig (Universidad Complutense de Madrid, Spain). The talk, which is entitled (Un)decidability in Petri nets with name creation and replication, will be held at 14:00 in room M1.05 at the new premises of Reykjavik University in Nauthólsvík.


The study of the expressive power of computation models in between Petri nets and Turing machines, and in particular of the class of
Well Structured Transition Systems, is a challenging research problem. In this talk I will present two orthogonal extensions of Petri nets, with the capability of creating and managing pure names, and with a replication primitive, getting nu-Petri nets and g-RN systems, respectively. First, I will show how these two extensions are strongly equivalent, but only when a garbage collection mechanism is added for idle threads. However, when both extensions are considered simultaneously, we obtain a Turing complete model, that we call nu-RN systems. Then I will survey the known expressivity results for nu-Petri nets (and therefore, for g-RN systems). In particular, coverability, boundedness and termination are decidable, while reachability and place-boundedness are undecidable, so that nu-Petri nets are strictly in between Petri nets and Turing machines. Then I will show how can we restrict nu-Petri nets (and, therefore, g-RN systems) and nu-RN systems in order to keep decidability of reachability and coverability, respectively.

As far as the audience will claim for it, I will start the presentation by a fast review of the main concepts around Petri Nets and Well Structured Transition Systems.

This is joint work with Fernando Rosa-Velardo.