| 講演名 | 1995/7/7 Pontryaginの最小原理によるペトリネットの可到達性解析の試み 松本 忠, タレク アハメド, サレー サリヘン, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 発火回数ベクトルuの存在を仮定したもとでの制約なしペトリネット(N,x_0)のx_dへの可到達問題(x_0:初期マーキングx_d:最終マーキング)を、uが未知の場合(最短時間制御問題)とuが既知の場合(最少トークン移動制御問題)の二つの場合について、Pontryaginの離散時間最小原理を適用して解いている。各部分問題の最小化は二つの場合ともに線形計画法(LP)を用いて非負整数解を求め得ること、発火ベクトルの制約条件の一つである臨界的サイフォンの探索手数と随伴方程式を解く手数を無視すれば、各部分最小化問題は多項式時間アルゴリズムで解けることになり、全体の最小化はこれをd回用いる準多項式時間アルゴリズムで解けることを示している。 |
| 抄録(英) | 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. |
| キーワード(和) | ペトリネット / 可到達性 / Pontryaginの離散時間最小原理 / 線形計画法 / 準多項式 / 時間アルゴリズム(条件付) |
| キーワード(英) | Petri nets / Reachability / Pontryagin's discrete-time minimum principle / Linear programing / Semi-polynomial time complexity |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 1995/7/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | Pontryaginの最小原理によるペトリネットの可到達性解析の試み |
| サブタイトル（和） | |
| タイトル（英） | A Study on Reachability for Petri Nets via Pontryagin's Minimum Principle |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 可到達性 / Reachability |
| キーワード(3)（和/英） | Pontryaginの離散時間最小原理 / Pontryagin's discrete-time minimum principle |
| キーワード(4)（和/英） | 線形計画法 / Linear programing |
| キーワード(5)（和/英） | 準多項式 / Semi-polynomial time complexity |
| キーワード(6)（和/英） | 時間アルゴリズム(条件付) |
| 第 1 著者 氏名（和/英） | 松本 忠 / Tadashi Matsumoto |
| 第 1 著者 所属（和/英） | 福井大学工学部 Faculty of Engineering, Fukui University |
| 第 2 著者 氏名（和/英） | タレク アハメド / Ahmed Tarek |
| 第 2 著者 所属（和/英） | 福井大学工学部 Faculty of Engineering, Fukui University |
| 第 3 著者 氏名（和/英） | サレー サリヘン / Salihen Saleh |
| 第 3 著者 所属（和/英） | 福井大学工学部 Faculty of Engineering, Fukui University |
| 発表年月日 | 1995/7/7 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 137 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |