| 講演名 | 2002/7/30 ペトリネットの極小サイフォン・トラップの抽出法GMSTと効率的インバリアント算出法への応用 田口 旭洋, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットN=(P,T,E,α,β)のsiphon-trapとは,以下の条件をみたすようなプレース集合Sである:「任意のトランジションtに対して,tからS内のプレースへの辺が存在するときかつそのときのみ,S内のプレースからtへの辺が存在する.」本稿では,互いに素な極小siphon-trapの極大族を抽出するO(|P|^2(|P|+|T|+|E|))時間アルゴリズムGMSTとその反復によるGMST_iを提案する。GMST_iでは,異なるsiphon-trapが必ずしも互いに素とは限らない.次に,ペトリネットインバリアント抽出法であるFourier-Motzkin法にGMSTを前処理として組込んだSTFM_Gを提案する.計算機実験により,GMST_iが従来手法と比べ、より高速により多くの極小siphon-trapが抽出できること、および、STFM_Gが既存手法よりもペトリネットの極小サポートP-インバリアントを1つ以上多く求める可能性がより高いアルゴリズムであることを示す. |
| 抄録(英) | A siphon-trap of a Petri net N = (P, T, E, α, β) is defined as a set S of places such that, for any transition t, there is an edge from t to a place of S if and only if there is an edge from a place of S to t. In this paper, we propose an O(|P|^2(|P|+|T|+|E|)) time algorithm GMST and another one GMST_i that repearts GMST i times. By incorporating GMST_i, into the Fourier-Motzkin method as preprocessing, we propose an algorithm STFM_G for computing minimal-support nonnegative integer invariants. It is shown, through experimental results, that GMST_i can extract more minimal siphon-traps and is faster than existing algorithms and that STFM_G has high possibility of finding, if any, at least one minimal-support nonnegative integer invariant. |
| キーワード(和) | ペトリネット / P-インバリアント / 極小サポート / 極小siphon-trap / Fourier-Motzkin法 |
| キーワード(英) | Petri nets / P-invariants / minimal supports / minimal siphon-straps / Fourier-Motzkin method |
| 資料番号 | CST2002-14 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2002/7/30(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ペトリネットの極小サイフォン・トラップの抽出法GMSTと効率的インバリアント算出法への応用 |
| サブタイトル（和） | |
| タイトル（英） | An algorithm GMST for extracting minimal siphon-traps and its application to efficient computation of Petri net invariants |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | P-インバリアント / P-invariants |
| キーワード(3)（和/英） | 極小サポート / minimal supports |
| キーワード(4)（和/英） | 極小siphon-trap / minimal siphon-straps |
| キーワード(5)（和/英） | Fourier-Motzkin法 / Fourier-Motzkin method |
| 第 1 著者 氏名（和/英） | 田口 旭洋 / Akihiro TAGUCHI |
| 第 1 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 2 著者 氏名（和/英） | 田岡 智志 / Satoshi TAOKA |
| 第 2 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 第 3 著者 氏名（和/英） | 渡邉 敏正 / Toshimasa WATANABE |
| 第 3 著者 所属（和/英） | 広島大学大学院 工学研究科 情報工学専攻 Graduate School of Engineering, Hiroshima University |
| 発表年月日 | 2002/7/30 |
| 資料番号 | CST2002-14 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 259 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |