Completeness Results for Single-Path Petri Nets

We define a new subclass of persistent Petri nets called single-path Petri nets. Our intention is to provide a class of Petri nets whose study might yield some insight into the mathematical properties of persistent Petri nets or even general Petri nets. We conjecture that the Karp-Miller coverability tree for a persistent net is small enough to be searched in polynomial space. Although we are unable to prove this conjecture, we do show that single-path Petri nets have this property. We then use this fact to show that the canonical analysis problems (i. e. , boundedness, reachability, containment, and equivalence) for single-path Petri nets are PSPACE-complete in the strong sense. Furthermore, we show that the problem of recognizing a single-path Petri net is also PSPACE-complete.

Authors

• R.R. Howell
• P. Jancar
• L.E. Rosier

Keywords

No keywords are indexed for this paper.