Computer Science – Logic in Computer Science
Scientific paper
2010-11-17
Computer Science
Logic in Computer Science
20 pages, 7 figures
Scientific paper
We prove several decidability and undecidability results for nu-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 nu-PN strictly surpasses that of P/T nets. We prove that nu-PN are Well Structured Transition Systems. In particular, we obtain decidability of coverability and termination, so that the expressive power of Turing machines is not reached. Moreover, they are strictly Well Structured, so that the boundedness problem is also decidable. We consider two properties, width-boundedness and depth-boundedness, that factorize boundedness. Width-boundedness has already been proven to be decidable. We prove here undecidability of depth-boundedness. Finally, we obtain Ackermann-hardness results for all our decidable decision problems.
Frutos-Escrig David de
Rosa-Velardo Fernando
No associations
LandOfFree
Decision Problems for Petri Nets with Names does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Decision Problems for Petri Nets with Names, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decision Problems for Petri Nets with Names will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-112594