Finding legal firing sequences of Petri nets by means of dynamic programming included linear programming
Tadashi Matsumoto, A. Tarek · 2002
There is no general useful method, except the reachability tree, to find legal firing sequences even for a bounded Petri net. An LP-based method with semi-polynomial-time-complexity for this problem with the m/spl times/1 known firing count vector u has been recently reported by Fujii et al (1994), but its disadvantage is that the size of constraints becomes exhaustive. For improving the above point, this paper proposes a DP-based method which can reduce about d/sup -1/ times the size of constraints for each subprocess and can also avoid the space explosion in DP by using some properties between a Petri net and its reversed net, where d is the length of firing sequence and is defined by d=/sup /spl Delta///spl Sigma//sub i=1//sup m/u/sub i/ and u=/sup /spl Delta//[u/sub i/]. Moreover, it is shown that each suboptimization can also be solved by LP with the polynomial time complexity. As a result of the above, this proposed method based on DP including d LPs is the algorithm with about d/sup -3/ times semi-polynomial time complexity compared with that given by Fujii et al. in which only one LP is applied to the given reachability problem.