*For the most recent entries see the
Petri Nets Newsletter.*

## Single-Path Petri Nets.

Howell, Rodney R.;
Jancar, Petr;
Rosier, Louis E.
*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.

*Do you need a refined search? Try our search engine
which allows complex field-based queries.*
*Back to the Petri Nets Bibliography*