Report TR--CS--90--20, pages 1-11 pp.. Manhattan, KS, USA: Kansas State University, Department of Computing and Information Sciences, December 1990.
Also in: Tarlecki, A.: Lecture Notes in Computer Science, Vol. 520; MFCS'91, Mathematical Foundations of Computer Science, 16th International Symposium, Kazimierz Dolny, Poland, Sep. 9-13, 1991, pages 202-210. Springer-Verlag, 1991.
Abstract: The authors define an new subclass of persistent Petri nets called single-path Petri nets. It is conjectured that the Karp-Miller coverability tree for a persistent net is small enough to be searched in polynomial space. Although the authors are unable to prove this conjecture, they do show that single-path Petri nets have this property. This fact is used to show that the canonical analysis problems (ie. boundedness, reachability, containment, equivalence) for single-path Petri nets are PSPACE-complete in the strong sense. Furthermore, the authors show that the problem of recognizing a single-path Petri net is also PSPACE-complete.
Keywords: single-path net; persistent net; coverability tree, polynomial space search; boundedness; reachability; containment; PSPACE completeness.