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

Volume

2

fYear

1997

fDate

9-12 Jun 1997

Firstpage

1017

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on

Print_ISBN

0-7803-3583-X

Type

conf

DOI

10.1109/ISCAS.1997.621907

Filename

621907