Shortest Paths in Reachability Graphs.

For the most recent entries see the Petri Nets Newsletter.

Shortest Paths in Reachability Graphs.

In: Ajmone Marsan, M.: Lecture Notes in Computer Science, Vol. 691; Application and Theory of Petri Nets 1993, Proceedings 14th International Conference, Chicago, Illinois, USA, pages 224-241. Springer-Verlag, 1993.

Also in: Journal of Computer and System Sciences, Vol. 51, No. 2, pages 314-323. 1995.

Abstract: We prove the following property for safe conflict-free Petri nets and live and safe extended free-choice Petri nets: Given two markings M₁, M₂ of the reachability graph, if some path leads from M₁ to M₂, then some path of polynomial length in the number of transitions of the net leads from M₁ to M₂.

Keywords: conflict-free Petri nets, free-choice Petri nets, marked graphs.

Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography