お知らせ 研究会の開催と会場に参加される皆様へのお願い(2020年7月開催~)
電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [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.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2011-11-17 14:50:00 
発表時間 25 
申込先研究会 MSS 
資料番号 IEICE-CAS2011-68,IEICE-MSS2011-37 
巻番号(vol) IEICE-111 
号番号(no) no.293(CAS), no.294(MSS) 
ページ範囲 pp.25-30 
ページ数 IEICE-6 
発行日 IEICE-CAS-2011-11-10,IEICE-MSS-2011-11-10 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会