| 講演名 | 1995/5/19 線形計画法を加味した動的計画法によるペトリネットの可到達性判定法 松本 忠, タレク アハメド, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットは、並列・並行、非同期、非決定な、分散・離散事象システムのモデルとして有用なものの1つとして関心がもたれているが、その基本的性質の可到達性の判定法としては、一般には、列挙法である可到達木を用いる以外に有用な手法はなかった。しかし、既知発火回数ベクトルのもとでの本問題はLPを直接に用いた多項式時間アルゴリズムで解けることが、最近、報告されたが、発火ベクトル系列長dとともに問題の規模が膨大になることが問題点の1つである[4]。本論文では、上記問題点を緩和させるために、与えられた可到達問題をd個の部分過程からなるものとみなし、Bellmanの最適性の原理によって得られる動的計画法DPによる定式化を行って、各部分過程の問題の規模を約1/dに縮小するとともに、一般のDPで問題になるメモリー空間の爆発をペトリネットの逆ネットの性質を活用することにより回避できること、更には、各部分問題の最適化もLPを用いて多項式時間で解けることを示している。その結果、本手法は、直接にLPを用いる場合[4]よりも約d^<-3>倍改善された多項式時間アルゴリズムであることが示されている。 |
| 抄録(英) | 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_ |
| キーワード(和) | ペトリネット / 可到達性 / 多項式時間アルゴリズム / 動的計画法 / 線形計画法 / メモリー空間爆発の回避 |
| キーワード(英) | Petri nets / Reachability / Polynomial-time-complexity / Dynamic programming / Linear programming / No memory-space explosion |
| 資料番号 | |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 1995/5/19(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 線形計画法を加味した動的計画法によるペトリネットの可到達性判定法 |
| サブタイトル（和） | |
| タイトル（英） | A method for deciding the reachability of Petri nets by means of dynamic programming included linear programming |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | 可到達性 / Reachability |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / Polynomial-time-complexity |
| キーワード(4)（和/英） | 動的計画法 / Dynamic programming |
| キーワード(5)（和/英） | 線形計画法 / Linear programming |
| キーワード(6)（和/英） | メモリー空間爆発の回避 / No memory-space explosion |
| 第 1 著者 氏名（和/英） | 松本 忠 / Tadashi Matsumoto |
| 第 1 著者 所属（和/英） | 福井大学工学部電子工学科 Faculty of Engineering, Fukui University |
| 第 2 著者 氏名（和/英） | タレク アハメド / Ahmed Tarek |
| 第 2 著者 所属（和/英） | 福井大学工学部電子工学科 Faculty of Engineering, Fukui University |
| 発表年月日 | 1995/5/19 |
| 資料番号 | |
| 巻番号（vol） | vol.95 |
| 号番号（no） | 46 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |