Rosa Velardo, FernandoFrutos Escrig, David De2023-06-202023-06-202010Rosa Velardo, F. & Frutos Escrig, D. «Decidability Problems in Petri Nets with Names and Replication». Fundamenta Informaticae, vol. 105, n.o 3, 2010, pp. 291-317. DOI.org (Crossref), https://doi.org/10.3233/FI-2010-368.0169-296810.3233/FI-2010-368https://hdl.handle.net/20.500.14352/43729In this paper we study decidability of several extensions of P/T nets with name creation and/or replication. In particular, we study how to restrict the models of RN systems (P/T nets extended with replication, for which reachability is undecidable) and ν-RN systems (RN extended with name creation, which are Turing-complete, so that coverability is undecidable), in order to obtain decidability of reachability and coverability, respectively. We prove that if we forbid synchronizations between the different components in a RN system, then reachability is still decidable. Similarly, if we forbid name communication between the different components in a ν-RN system, or restrict communication so that it is allowed only for a given finite set of names, we obtain decidability of coverability. Finally, we consider a polyadic version of ν-PN (P/T nets extended with name creation), that we call pν-PN, in which tokens are tuples of names. We prove that pν-PN are Turing complete, and discuss how the results obtained for ν-RN systems can be translated to them.engjournal articlehttps//doi.org/10.3233/FI-2010-368http://iospress.metapress.com/content/w7873089r71556h3/fulltext.pdfrestricted access004Petri netsPure namesInfinite state systemsDecidabilityMultithreadingSecurityChoreographyInformática (Informática)1203.17 Informática