| 講演名 | 2000/1/18 ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装 山内 雅弘, 西内 啓介, 渡邊 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットN=(P, T, E)のインバリアントとは, NのPT接続行列をAとした場合にA・X=0を満たすX(T-インバリアント)またはY^t・A=0を満たすY(P-インバリアント)である.非負整数インバリアント算出法としてよく知られるFourier-Motzkin(FM)法には, 途中で記憶すべき解候補ベクトルの増加に起因するメモリ不足のために計算が中断され, インバリアントが存在するにもかかわらず算出されない場合がある.我々は, 極小サイフォンかつトラップであるネット上での計算へと縮小することによってこの欠点を克服する方向で算出法STFMを既に報告した.本稿では, 解候補ベクトルの増加を抑えるための計算順序あるいはベクトル消去に関する幾つかの改良アイデアをFM法およびSTFM法に実装し, 候補ベクトル数が著しく減少すること, および計算時間が短縮されることを, 実験によって示す. |
| 抄録(英) | An invariant of a Petri net N=(P, T, E)is a |T|-dimensional vector X(a T-invariant)with A・X=0(zero vector)or a |P|-dimensional vector Y(a P-invariant)with Y^t・A=0 for the place-transition incidence matrix A of N. The Fourier-Motzkin(FM)method is well-known for computing all such nonnegative integer invariants. This method, however, has a critical deficiency: computation may be interrupted and no output is given because of memory overflow in storing intermediary vectors which are candidates for invariants. In order to overcome this deficiency, STFM has been proposed: it reduces the computation to smaller subnets based on siphons and tarps. The paper considers another direction of improvement: finding appropriate order of computation or deleting useless vectors so as not to increase the number of candidate vectors. Several ideas for such improvement are incorporated in both FM method and STAF. Their effects are experimentally evaluated, and some of them show great improvement. |
| キーワード(和) | ペトリネットインバリアント / 極小サポート / サイフォン / トラップ / Fourier-Motzkin法 |
| キーワード(英) | Petri net invariants / minimal supports / siphons / traps / the Fourier-Motzkin metod |
| 資料番号 | CST99-56 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2000/1/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ペトリネットインバリアント算出のためのFourier-Motzkin法の改良実装 |
| サブタイトル（和） | |
| タイトル（英） | Improved Implementation of the Fourier-Motzkin Method for Computing Petri Net Invariants |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネットインバリアント / Petri net invariants |
| キーワード(2)（和/英） | 極小サポート / minimal supports |
| キーワード(3)（和/英） | サイフォン / siphons |
| キーワード(4)（和/英） | トラップ / traps |
| キーワード(5)（和/英） | Fourier-Motzkin法 / the Fourier-Motzkin metod |
| 第 1 著者 氏名（和/英） | 山内 雅弘 / Masahiro Yamauchi |
| 第 1 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 西内 啓介 / Keisuke Nishiuchi |
| 第 2 著者 所属（和/英） | 広島大学工学部 第二類 回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邊 敏正 / Toshimasa Watanabe |
| 第 3 著者 所属（和/英） | 広島大学工学部 第二類 回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 2000/1/18 |
| 資料番号 | CST99-56 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 539 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |