| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2007-08-31 15:10 ペトリネットのサイフォン・トラップ抽出に基づくFourier-Motzkin法の安定性向上 ○近田智宏・田岡智志・渡邉敏正（広島大）  CST2007-16 |
|
| 抄録 | （和） | ペトリネットN = (P,T,E,α,β) のP-インバリアントとは、NのPT接続行列Aに対して「Y^t・A = 0 を満たす|P|次元ベクトルY」である。全ての非負整数極小サポートインバリアント抽出法としてよく知られるFourier-Motzkin(FM)法には、途中で記憶すべき解候補ベクトルの爆発的増加に起因するメモリ不足のために、インバリアントが存在するにも関わらず何も算出されない場合が起り得る。この欠点を回避し、より多くの極小サポートインバリアントを求めるために、Nの部分ネットであるサイフォン・トラップを抽出し、それにFM法を適用する手法STFM_Nが提案されている。本稿では、STFM_Nのサイフォン・トラップネット抽出法にNのトランジションの点次数を考慮した改良を加えた手法STFM_N+を提案し、計算機実験により、既存手法よりメモリ不足の発生を抑え、結果的に極小サポートインバリアントが求まる場合を増やすことを示す。 |
| （英） | For a Petri net = (P,T,E,α,β,), a P-invariant is a |P|-deimentional vector Y with Y^t・A = 0 for the place-transition incidence matrix A of N. The Fourier-Motzkin method is well-known for computing all such minimal-support nonnegative integer invariants(ms-invariants, for short). This method, however, has a critical deficiency such that, even if a give Petri net N has any invariant, it is likely that no invariants are output because of memory overflow in storing intermediary vectors as candidates for invariants. In order to overcome this deficiency, an algorithm STFM_N has been proposed for computation of ms-invariants: it tries to decrease the number of such candidate vectors by restricting computation of invariants to siphon-trap nets that are subnets of N. In this paper, we propose an algorithm STFM_N+, an improved version of STFM_N, by incorporating a new method that extracts siphon-trap nets by taking vertex-degrees of transitions of N into consideration. It is shown, through experiment results, that STFM_N+ can make occurrence of memory overflows less possible than STFM_N, implying that STFM_N+ has higher possibility of finding, if any, at least one ms-invariant. | |
| キーワード | （和） | ペトリネット / P-インバリアント / 極小サポート / メモリ不足 / サイフォン・トラップ / / / |
| （英） | Petri nets / P-invariants / minimal supports / memory overflows / siphon-traps / / / | |
| 文献情報 | 信学技報, vol. 107, 2007年8月. | |
| 資料番号 | ||
| 発行日 | 2007-08-24 (CST) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CST2007-16 |
|
| 研究会情報 | |
| 研究会 | MSS |
| 開催期間 | 2007-08-31 - 2007-08-31 |
| 開催地（和） | 島根大学総合理工学部多目的ホール |
| 開催地（英） | Shimane University |
| テーマ（和） | コンカレントシステム、離散事象システム、ハイブリッドシステム、および一般 |
| テーマ（英） | Concurrent Systems, Discrete Event Systems and Hybrid Systems |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2007-08-CST |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | ペトリネットのサイフォン・トラップ抽出に基づくFourier-Motzkin法の安定性向上 |
| サブタイトル（和） | |
| タイトル（英） | Enhancing Stability of the Fourier-Motzkin Method based on Siphon-Trap Extraction of Petri Nets |
| サブタイトル（英） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | P-インバリアント / P-invariants |
| キーワード(3)（和/英） | 極小サポート / minimal supports |
| キーワード(4)（和/英） | メモリ不足 / memory overflows |
| キーワード(5)（和/英） | サイフォン・トラップ / siphon-traps |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 近田 智宏 / Tomohiro Chikada / |
| 第1著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 田岡 智志 / Satoshi Taoka / |
| 第2著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 渡邉 敏正 / Toshimasa Watanabe / |
| 第3著者 所属（和/英） | 広島大学 (略称： 広島大) Hiroshima University (略称： Hiroshima Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2007-08-31 15:10:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CST2007-16 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | no.203 |
| ページ範囲 | pp.31-36 |
| ページ数 | 6 |
| 発行日 | 2007-08-24 (CST) |
[研究会発表申込システムのトップページに戻る]