International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 57, Pages 3023-3036
doi:10.1155/S0161171204403378
Lower and upper bounds of shortest paths in reachability graphs
Department of Applied Mathematics, Birla Institute of Technology, Mesra, Ranchi 835215, India
Received 22 March 2004
Copyright © 2004 P. K. Mishra. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
We prove the following property for safe marked
graphs, safe conflict-free Petri nets, and live and safe extended
free-choice Petri nets. We prove the following three results.
If the Petri net is a marked graph, then the length of the
shortest path is at most
(|T|−1)⋅|T|/2.
If the Petri net is conflict free, then the length
of the shortest path is at most
(|T|+1)⋅|T|/2.
If the petrinet is live and extended free choice, then
the length
of the shortest path is at most
|T|⋅|T+1|⋅|T+2|/6,
where T is the set of transitions of the net.