RT Journal Article
T1 Decidability and complexity of Petri nets with unordered data
A1 Rosa Velardo, Fernando
A1 Frutos Escrig, David De
AB We 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.
PB Elsevier Science
SN 0304-3975
YR 2011
FD 2011-08
LK https://hdl.handle.net/20.500.14352/43727
UL https://hdl.handle.net/20.500.14352/43727
LA eng
NO Rosa 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.
NO Comunidad de Madrid
NO Ministerio de Ciencia, Innovación y Universidades (España)
NO Ministerio de Educación, Formación Profesional y Deportes (España)
DS Docta Complutense
RD 17 abr 2025