Title :
Finding legal firing sequences in submarking reachability problems of Petri nets by discrete-time Pontryagin´s minimum principle
Author :
Matsumoto, Tadashi
Author_Institution :
Fac. of Eng., Fukui Univ., Japan
Abstract :
The relaxed problems for SMR⊃MR have been formulated by PMP with a free terminal time; SMR using Theorem Al and MR using Corollary Al; note that MR-FV has been solved by PMP-LP with a fixed terminal time. Secondly, we have proven that each problem for SMR⊃MR can have nonnegative integer solution by using PMP-LP of which time complexity is semi-polynomial time in live TCC and SCC nets. But, checking critical siphons at each time is needed in the upper classes. We have also assured the above execution by computer simulations. These approaches can give useful approximation algorithms for various important reachability problems in practical applications
Keywords :
Petri nets; computational complexity; discrete time systems; linear programming; maximum principle; reachability analysis; Petri nets; critical siphons; discrete-time Pontryagin´s minimum principle; free terminal time; legal firing sequences; nonnegative integer solution; semi-polynomial time; submarking reachability problems; time complexity; Cities and towns; Concurrent computing; Fires; Large-scale systems; Law; Legal factors; Linear programming; Optimal control; Petri nets; Vectors;
Conference_Titel :
Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on
Print_ISBN :
0-7803-3583-X
DOI :
10.1109/ISCAS.1997.621907
