Rosa Velardo, FernandoFrutos Escrig, David De2023-06-202023-06-202011-08Rosa Velardo, F. & Frutos Escrig, D. «Decidability and Complexity of Petri Nets with Unordered Data». Theoretical Computer Science, vol. 412, n.o 34, agosto de 2011, pp. 4439-51. DOI.org (Crossref), https://doi.org/10.1016/j.tcs.2011.05.007.0304-397510.1016/j.tcs.2011.05.007https://hdl.handle.net/20.500.14352/43727We prove several decidability and undecidability results for ν-PN, an extension of P/T nets with pure name creation and name management. We give a simple proof of undecidability of reachability, by reducing reachability in nets with inhibitor arcs to it. Thus, the expressive power of ν-PN strictly surpasses that of P/T nets. We encode ν-PN into Petri Data Nets, so that coverability, termination and boundedness are decidable. Moreover, we obtain Ackermann-hardness results for all our decidable decision problems. Then we consider two properties, width-boundedness and depth-boundedness, that factorize boundedness. Width-boundedness has already been proven to be decidable. Here we prove that its complexity is also non-primitive recursive. Then we prove undecidability of depth-boundedness. Finally, we prove that the corresponding “place version” of all the boundedness problems is undecidable for ν-PN. These results carry over to Petri Data Nets.engjournal articlehttps//doi.org/10.1016/j.tcs.2011.05.007http://www.sciencedirect.com/science/article/pii/S0304397511003896restricted access004Petri netsPure namesWell-structured transition systemsReachabilityBoundednessInformática (Informática)1203.17 Informática