| 講演名 | 1999/7/22 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN 和久田 真浩, 山内 雅弘, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットN=(P, T, E)のプレーストランジション-接続行列をAとするとき,Y^T・A=0の解YをNのP-インバリアント, A・X=0の非負整数解XをNのT-インバリアントという。インバリアントYまたはXの非零要素集合をそのサポートと呼び, 極小サポートを持つインバリアントを初等的インバリアントという。本稿は, 与えられた指定ノード集合Qを含むサポートを持つインバリアントを1つ, 複数, あるいはすべて, 算出するアルゴリズムFMSNを提案し, 実験によりその実用性を示す。ここで, P-インバリアントではQ⊆P, T-インバリアントではQ⊆Tとする。 |
| 抄録(英) | The paper proposes a fast and space saving algorithm FMSN for computing, if any, one or more elementary invariants each of whose support contains a specified set Q of nodes in a given Petri net. It is a combination of the Fourier-Motzkin method and the algorithm HBFB for extracting all minimal siphons containing Q. It does not seem that computing such invariants has ever been discussed explicitly. The main point is that FMSN tries to decrease the number of candidate vectors by restricting computation of invariants to P-siphons or T-siphons that are P-traps or T-traps containing Q, respectively. Experimental results show that incorporating this restriction into the Fourier-Motzkin method greatly reduces the maximum number of candidate vectors, making FMSN a promising algorithm. |
| キーワード(和) | ペトリネットインバリアント / 極小サポート / 初等的インバリアント / 算出アルゴリズム / プレーストランジション接続行列 |
| キーワード(英) | Petri net invariants / minimal support / elementary invariants / computing algorithm / place-transition incidence matrices |
| 資料番号 | CST99-16 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 1999/7/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 指定ノード集合を含むサポートを持つペトリネットインバリアントの算出アルゴリズムFMSN |
| サブタイトル（和） | |
| タイトル（英） | A Fast and Space-Saving Algorihtm FMSN for Computing Petri Net Invariants with Supports Containing All Specified Nodes |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネットインバリアント / Petri net invariants |
| キーワード(2)（和/英） | 極小サポート / minimal support |
| キーワード(3)（和/英） | 初等的インバリアント / elementary invariants |
| キーワード(4)（和/英） | 算出アルゴリズム / computing algorithm |
| キーワード(5)（和/英） | プレーストランジション接続行列 / place-transition incidence matrices |
| 第 1 著者 氏名（和/英） | 和久田 真浩 / Masahiro Wakuda |
| 第 1 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 山内 雅弘 / Masahiro Yamauchi |
| 第 2 著者 所属（和/英） | 広島大学大学院工学研究科情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 田岡 智志 / Satoshi Taoka |
| 第 3 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 第 4 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa Watanabe |
| 第 4 著者 所属（和/英） | 広島大学工学部第二類回路システム工学講座 Department of Circuits and Systems, Faculty of Engineering, Hiroshima University |
| 発表年月日 | 1999/7/22 |
| 資料番号 | CST99-16 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 206 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |