A Study on Reachability for Petri Nets via Pontryagin's Minimum Principle

MATSUMOTO Tadashi, TAREK Ahmed, SALEH Salihen

Bibliographic Information

Other Title

Pontryagin の最小原理によるペトリネットの可到達性解析の試み

Description

Reachability problem from the given initial marking x_0 to the given determination marking x_d is discussed on the assumtion that the existence of the firing count vector-u, is guranteed, in which two cases, (1)u is unknown (the minimum time control problem) and (2)u is known (the minimum transfer-tokens control problem), are solved by applying Pontryagin's discrete-time minimum) principle to the above relaxed reachability problem. It is shown that a nonnegative integer solution for each minimization subproblem in both two cases is obtained by linear programing and that the time-complexity for each subproblem is polynomial, while that for the given original problem is semi-polynomial, if the special procedure solving adjoint equation and finding critical siphons which are one of control-vector-constraints is neglected.

Journal

Technical report of IEICE. CST

Technical report of IEICE. CST 95 (137), 7-14, 1995-07-07

The Institute of Electronics, Information and Communication Engineers

Keywords

Details 詳細情報について

CRID: 1570572702490700928

NII Article ID: 110003300047

NII Book ID: AN10438446

Text Lang: ja

Data Source

CiNii Articles

Export

Report a problem