RT Book, Section
T1 Decidability results for restricted models of petri nets with name creation and replication
A1 Rosa Velardo, Fernando
A1 Frutos Escrig, David De
A2 Francescinis, Giuliana
A2 Wolf, Karsten
AB In previous works we defined ν-APNs, an extension of P/T nets with the capability of creating and managing pure names. We proved that, though reachability is undecidable, coverability remains decidable for them. We also extended P/T nets with the capability of nets to replicate themselves, creating a new component, initially marked in some fixed way, obtaining g-RN systems. We proved that these two extensions of P/T nets are equivalent, so that g-RN systems have undecidable reachability and decidable coverability. Finally, for the class of the so called ν-RN systems, P/T nets with both name creation and replication, we proved that they are Turing complete, so that also coverability turns out to be undecidable. In this paper we study how can we restrict the models of ν-APNs (and, therefore, g-RN systems) and ν-RN systems in order to keep decidability of reachability and coverability, respectively. We prove that if we forbid synchronizations between the different components in a g-RN system, then reachability is still decidable. The proof is done by reducing it to reachability in a class of multiset rewriting systems, similar to Recursive Petri Nets. Analogously, if we forbid name communication between the different components in a ν-RN system, or restrict communication to happen only for a given finite set of names, we obtain decidability of coverability.
PB Springer
SN 978-3-642-02423-8
YR 2009
FD 2009
LK https://hdl.handle.net/20.500.14352/53230
UL https://hdl.handle.net/20.500.14352/53230
LA eng
NO Rosa Velardo, F. & Frutos Escrig, D. «Decidability Results for Restricted Models of Petri Nets with Name Creation and Replication». Applications and Theory of Petri Nets, editado por Giuliana Franceschinis y Karsten Wolf, vol. 5606, Springer Berlin Heidelberg, 2009, pp. 63-82. DOI.org (Crossref), https://doi.org/10.1007/978-3-642-02424-5_6.
DS Docta Complutense
RD 6 abr 2025