| 講演名 | 2001/7/17 ペトリネットの極小サイフォン・トラップ抽出アルゴリズムとそのP-インバリアント計算への応用 高野 勝史, 田岡 智志, 渡邉 敏正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | ペトリネットN=(P, T, E, α, β)のsiphon-trap(ST台)とは, 以下の条件をみたすようなプレース集合Sである:「任意のトランジションtに対して, tからS内のプレースへの辺が存在するときかつそのときのみ, S内のプレースからtへの辺が存在する.」本稿では, 互いに素な極小ST台の極大族をO(|P|^2(|P|+|T|+|E|))時間で抽出するアルゴリズムFDSTを提案し, かつFDSTのペトリネットインバリアント計算への応用を述べる.NのP-インバリアントとは, NのPT接続行列をAとした場合にY^t・A=0を満たす解Yである.本稿では非負整数P-インバリアントのみを対象とする.このとき, 任意のP-インバリアントは極小サポートP-インバリアントの非負有理係数の線形和によって表すことができるため, 極小サポートインバリアントを求める.FDSTの応用として, 極小サポートP-インバリアントの高速算出法STFM_Tを提案し, 計算機実験によりその有用性を示す. |
| 抄録(英) | 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 FDST that produces a maximal class of mutually disjoint minimal siphon-traps of a given Petri net, and its application to P-invariant computation is shown. An P-invariant of N is a |P|-dimensional vector Y with Y^t・A=0 for the place-transition incidence matrix A of N. Only nonnegative integer P-invariants are considered in this paper. Since any invariant is expressed as a linear combination of minimal-support P-invariants(ms-P-invariants for short)with nonnegative rational coefficients, we try to obtain some or all ms-P-invariants. As an application of FDST, we propose a fast algorithm STFM_T for computing one or more ms-P-invariants, and its usefulness is shown through experimental results. |
| キーワード(和) | ペトリネット / P-インバリアント / 極小ST台 / Fourier-Motzkin法 |
| キーワード(英) | Petri nets / P-invariants / minimal siphon-straps / Fourier-Motzkin method |
| 資料番号 | CST2001-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | CST |
|---|---|
| 開催期間 | 2001/7/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Concurrent System Technology (CST) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | ペトリネットの極小サイフォン・トラップ抽出アルゴリズムとそのP-インバリアント計算への応用 |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Extracting Minimal Siphon-traps of Petri Nets and its Application to P-Invariant Computation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ペトリネット / Petri nets |
| キーワード(2)（和/英） | P-インバリアント / P-invariants |
| キーワード(3)（和/英） | 極小ST台 / minimal siphon-straps |
| キーワード(4)（和/英） | Fourier-Motzkin法 / Fourier-Motzkin method |
| 第 1 著者 氏名（和/英） | 高野 勝史 / Katsushi Takano |
| 第 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 |
| 発表年月日 | 2001/7/17 |
| 資料番号 | CST2001-12 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 212 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |