Presentation	1995/5/19 A method for deciding the reachability of Petri nets by means of dynamic programming included linear programming Tadashi Matsumoto, Ahmed Tarek,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Petri nets are a graphical and mathematical modeling tool applicable to many systems that are characterized as being concurrent, asynchronous, distributed, parallel, and/or nondeterministic. Although reachability is a fundamental basis for studying the dynamic properies of Petri nets, there is no general useful method except the reachability tree to decide it even for a bounded Petri net. An LP-based method with polynomial-time-complexity for this problem with the m × 1 known firing count vector u has been recently reported in [4], 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^<-1> times the size of contraints 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 =^^Δ Σ^m_ u_i and u =^^Δ [u_i]. Moreover, it is shown that each suboptimization can be also 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^<-3> times polynomial-time-complexity compared with that of [4] in which only one LP is applied to the given reachability problem.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Petri nets / Reachability / Polynomial-time-complexity / Dynamic programming / Linear programming / No memory-space explosion
Paper #
Date of Issue

Conference Information
Committee	CST
Conference Date	1995/5/19(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Concurrent System Technology (CST)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	A method for deciding the reachability of Petri nets by means of dynamic programming included linear programming
Sub Title (in English)
Keyword(1)	Petri nets
Keyword(2)	Reachability
Keyword(3)	Polynomial-time-complexity
Keyword(4)	Dynamic programming
Keyword(5)	Linear programming
Keyword(6)	No memory-space explosion
1st Author's Name	Tadashi Matsumoto
1st Author's Affiliation	Faculty of Engineering, Fukui University()
2nd Author's Name	Ahmed Tarek
2nd Author's Affiliation	Faculty of Engineering, Fukui University
Date	1995/5/19
Paper #
Volume (vol)	vol.95
Number (no)	46
Page	pp.pp.-
#Pages	8
Date of Issue