| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2011-11-17 14:50 トラップ包含閉路ネットの判定法 ○太田 淳・辻 孝吉（愛知県立大）  CAS2011-68 MSS2011-37 |
|
| 抄録 | （和） | ペトリネットはコンカレントシステムのための有効なモデルの一つである。 一般にペトリネットの解析問題には膨大な計算量が必要である。 ペトリネットの構造を制約して、ある範囲の問題を表現可能であり、かつ、計算量が軽減されるサブクラスが提案されている。本報告では、そのようなサブクラスのうちトラップ閉路(TC)ネット、構造的弱パーシステントネット(SWPN)、トラップ包含閉路(TCC)ネットを取り扱う。 与えられたネットがこれらのサブクラスであることを検証する計算量は、TCネットは多項式時間、残りの2つのネットは補NP完全であることが知られている。 著者らはTCネットの検証問題を線形計画問題に帰着させる方法を提案した。 本報告では、TCネットのグラフ理論的検証、および、SWPN, TCCネットの検証問題の論理式の充足可能性問題への帰着について考察する。 後者は、Oaneaによるトラップを包含しないサイフォンの検出方法を応用した方法である。 |
| （英） | Petri net is a graphical and mathematical modeling tool for concurrent systems. Analysis of general Petri net requires vast computational cost. There are some subclasses of Petri net with less computational complexity and moderate modeling power. In this report, three subclasses are considered: trap circuit nets (TC), structurally weak persistent nets (SWPN) and trap containing circuit net (TCC). TC net can be verified in polynomial time, which is shown by reducing the problem to linear programming. Verification problems of other two subclasses have been proved to be co-NP complete. This report shows graph theoretic method to verify TC nets. SWPN and TCC nets can be verified by reducing them to satisfiability problems of boolean expression, which are based on the method proposed by Oanea et al. to detect siphon containing no traps. |
|
| キーワード | （和） | 並行システム / 並行システム / サブクラス / 検証問題 / 充足可能性問題 / / / |
| （英） | concurrent system / Petri net / verification of subclasses / satisfiability problem / / / / | |
| 文献情報 | 信学技報, vol. 111, no. 294, MSS2011-37, pp. 25-30, 2011年11月. | |
| 資料番号 | MSS2011-37 | |
| 発行日 | 2011-11-10 (CAS, MSS) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | CAS2011-68 MSS2011-37 |
|
| 研究会情報 | |
| 研究会 | CAS MSS |
| 開催期間 | 2011-11-17 - 2011-11-18 |
| 開催地（和） | 山口大学大学会館 |
| 開催地（英） | Univ. of Yamaguchi |
| テーマ（和） | グラフ、ペトリネット、ニューラルネット、および一般 |
| テーマ（英） | Graph, Petri Net, Neural network, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | MSS |
| 会議コード | 2011-11-CAS-MSS |
| 本文の言語 | 日本語 |
| タイトル（和） | トラップ包含閉路ネットの判定法 |
| サブタイトル（和） | |
| タイトル（英） | On some algorithm to verify trap ccontaining circuit nets. |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 並行システム / concurrent system |
| キーワード(2)（和/英） | 並行システム / Petri net |
| キーワード(3)（和/英） | サブクラス / verification of subclasses |
| キーワード(4)（和/英） | 検証問題 / satisfiability problem |
| キーワード(5)（和/英） | 充足可能性問題 / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 太田 淳 / Atsushi Ohta / オオタ アツシ |
| 第1著者 所属（和/英） | 愛知県立大学 (略称： 愛知県立大) Aichi Prefectural University (略称： Aichi Pref. Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 辻 孝吉 / Kohkichi Tsuji / ツジ コウキチ |
| 第2著者 所属（和/英） | 愛知県立大学 (略称： 愛知県立大) Aichi Prefectural University (略称： Aichi Pref. Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-11-17 14:50:00 |
| 発表時間 | 25分 |
| 申込先研究会 | MSS |
| 資料番号 | CAS2011-68, MSS2011-37 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.293(CAS), no.294(MSS) |
| ページ範囲 | pp.25-30 |
| ページ数 | 6 |
| 発行日 | 2011-11-10 (CAS, MSS) |
[研究会発表申込システムのトップページに戻る]