文献

J-GLOBAL ID：201302272358180200   整理番号：13A0070711

ペトリネットの状態数の多項式時間計算について~有界性と入れ子構造を活用したアプローチ~

著者 (2件)： 洲崎武史 (山口大 大学院理工学研究科) ,  山口真悟 (山口大 大学院理工学研究科)
資料名： 情報処理学会研究報告(CD-ROM)
巻： 2012  号： 4  ページ： ROMBUNNO.AL-142,NO.3  発行年： 2012年12月15日 
JST資料番号： Z0031C  ISSN： 2186-2583  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： ペトリネットの振舞いに関する問題は,その状態空間を調べることにより解くことができる。状態空間そのものを求めることは,そのサイズがペトリネットのサイズの指数関数オーダーになる場合があるので,手に負えない。しかしながら,状態空間のサイズ(状態数)であれば,多項式時間で求められる可能性がある。状態数を求めることができれば,状態空間を求めるために必要な時間やメモリを見積もることが可能となる。本稿ではペトリネットの状態数計算問題を定式化し,その複雑さを明らかにする。さらにサブクラスに対して多項式時間の計算法を提案する。(著者抄録)

シソーラス用語： *Petriネット ,  *アルゴリズム ,  *計算量 ,  空間 ,  数値 ,  性能分析 ,  記憶容量 ,  状態遷移図 ,  *離散系
準シソーラス用語： *多項式時間アルゴリズム ,  入れ子型 ,  状態空間 ,  状態数 ,  *離散事象系

分類 (3件)： ネットワーク法  (KA03040X) ,  計算理論  (JB02000A) ,  システムモデル  (IB02000Z)

タイトルに関連する用語 (6件)： ペトリネット ,  多項式時間 ,  計算 ,  有界 ,  入れ子構造 ,  活用