@article{RosaVelardo20114439,
    Abstract = {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.},
    Author = {Rosa-Velardo, Fernando and de Frutos-Escrig, David},
    File = {Decidability and complexity of Petri nets with unordered data - Rosa-Velardo, Frutos-Escrig (0) (0) - a - a - m.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {Boundedness},
    Number = {34},
    Pages = {4439 - 4451},
    Title = {Decidability and complexity of Petri nets with unordered data},
    URL = {http://www.sciencedirect.com/science/article/pii/S0304397511003896},
    Volume = {412},
    Year = {2011},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397511003896},
    bdsk-url-2 = {http://dx.doi.org/10.1016/j.tcs.2011.05.007},
    date-added = {2015-05-14 15:58:50 +0000},
    date-modified = {2015-05-14 15:58:50 +0000},
    doi = {10.1016/j.tcs.2011.05.007}
}

@article{RosaVelardo20114439, Abstract = {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.}, Author = {Rosa-Velardo, Fernando and de Frutos-Escrig, David}, File = {Decidability and complexity of Petri nets with unordered data - Rosa-Velardo, Frutos-Escrig (0) (0) - a - a - m.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {Boundedness}, Number = {34}, Pages = {4439 - 4451}, Title = {Decidability and complexity of Petri nets with unordered data}, URL = {http://www.sciencedirect.com/science/article/pii/S0304397511003896}, Volume = {412}, Year = {2011}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/S0304397511003896}, bdsk-url-2 = {http://dx.doi.org/10.1016/j.tcs.2011.05.007}, date-added = {2015-05-14 15:58:50 +0000}, date-modified = {2015-05-14 15:58:50 +0000}, doi = {10.1016/j.tcs.2011.05.007} }