2026-06-27T23:22:59Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/532302024-07-10T15:40:29Zcom_20.500.14352_14col_20.500.14352_21
Docta Complutense
author
Rosa Velardo, Fernando
author
Frutos Escrig, David De
editor
Francescinis, Giuliana
editor
Wolf, Karsten
2023-06-20T13:39:17Z
2023-06-20T13:39:17Z
2009
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.
978-3-642-02423-8
10.1007/978-3-642-02424-5_6
https://hdl.handle.net/20.500.14352/53230
https//doi.org/10.1007/978-3-642-02424-5_6
http://link.springer.com/content/pdf/10.1007%2F978-3-642-02424-5_6.pdf
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.
eng
Decidability results for restricted models of petri nets with name creation and replication
book part
URL
https://docta.ucm.es/bitstreams/4fc6fd92-306e-4284-bbb1-bea45d19eac2/download
File
MD5
bc36af01362757fd8c5b1685798e99e5
429403
application/pdf
Frutos48springer.pdf