ペトリネットの状態数の多項式時間計算について〜有界性と入れ子構造を活用したアプローチ〜
スポンサーリンク
概要
- 論文の詳細を見る
ペトリネットの振舞いに関する問題は,その状態空間を調べることにより解くことができる.状態空間そのものを求めることは,そのサイズがペトリネットのサイズの指数関数オーダーになる場合があるので,手に負えない.しかしながら,状態空間のサイズ (状態数) であれば,多項式時間で求められる可能性がある.状態数を求めることができれば,状態空間を求めるために必要な時間やメモリを見積もることが可能となる.本稿ではペトリネットの状態数計算問題を定式化し,その複雑さを明らかにする.さらにサブクラスに対して多項式時間の計算法を提案する.
- 2012-10-26
著者
関連論文
- 自由選択ワークフローネットのWell-Structuredワークフローネットへのリファクタリングについて
- 自由選択ワークフローネットのWell-Structuredワークフローネットへのリファクタリングについて
- A-12-1 Well-Structuredワークフローネットへのリファクタリングの提案(A-12.コンカレント工学,一般セッション)
- アクションを共有するワークフローネットに対する振る舞い継承と健全性を満たす合成規則(ペトリネット,離散事象システム,一般)
- ワークフローネットの健全性判定に対するモデル検査法について
- CSTソリューションコンペティション2007及び2008の総括(ペトリネット,離散事象システム,一般)
- AI-2-1 CSTソリューションコンペティション2008 : 総括(AI-2.CSTソリューションコンペティション2008:表彰式・シンポジウム,ソサイエティ企画)
- A-12-2 Acyclic well-structuredワークフローネットに対する直列化可能性判定法の提案(A-12.コンカレント工学,一般セッション)
- A-12-3 ワークフローネットにおける関心事とその強調法について(A-12.コンカレント工学,一般セッション)
- D-15-15 プロジェクトマネジメントのパターンを学習するための問題集と手引き集の開発(D-15. 教育工学,一般セッション)
- 引継型と請負型のインターワークフローへの動的変更の解析
- 不活性なトランジションを持つワークフローネットのProtocol継承を考慮した健全化について(グラフ,ペトリネット,ニューラルネット,及び一般)
- AK-2-3 マルチカーエレベータ群管理アルゴリズムに関する研究動向 : CSTソリューションコンペティション2007の活動を通じて(AK-2.基礎・境界分野の研究最前線,ソサイエティ特別企画,ソサイエティ企画)
- AI-1-5 CSTソリューションコンペティション2007(総括)(AI-1. CSTソリューションコンペティション2007:表彰式・シンポジウム,依頼シンポジウム,ソサイエティ企画)
- AS-3-4 CSTソリューションコンペティション2010の概要 : マルチカーエレベータの最適制御(AS-3.コンカレントシステム理論の最近の発展とその応用,シンポジウムセッション)
- A-12-8 CSTソリューションコンペティション2007 : 課題と評価ツール(A-12.コンカレント工学,一般講演)
- AP-2-5 CSTソリューションコンペティション2007(概要)(AP-2.コンカレント技術研究の方向性,パネル討論,ソサイエティ企画)
- A-12-4 デバイスドライバのネット指向テーラーメイド設計システムの提案(A-12.コンカレント工学,一般セッション)
- 不活性なトランジションを持つワークフローネットのProtocol継承を考慮した健全化について(グラフ,ペトリネット,ニューラルネット,及び一般)
- Acyclic拡張自由選択ワークフローネットに対する直列化可能性のリファクタリングによる判定方法の提案(一般)
- CSTソリューションコンペティション2010 : マルチカーエレベータの最適制御(CSTソリューションコンペティション2010,コンカレントシステム及び一般)
- シグナル伝達経路ペトリネットモデルにおける遅延時間の整合性確認手法の提案(一般,コンカレントシステム及び一般)
- AS-3-6 ワークフローネットの解析問題と解析能力(AS-3.ワークフローとビジネスプロセス管理への数理的アプローチ,シンポジウムセッション)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- システムと信号処理サブソの新たな展開を目指して(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- リスクパターンベースの構築とプロジェクト実践授業におけるリスク特定への応用(プロジェクトと組織のリスク)
- 拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について (システム数理と応用)
- A-12-2 時間ペトリネットから時間オートマトンへのコンパクトな変換について(A-12.システム数理と応用,一般セッション)
- ペトリネットの状態数の多項式時間計算について〜有界性と入れ子構造を活用したアプローチ〜
- 単純Well-Structuredワークフローネットの諸性質(グラフ,ペトリネット,ニューラルネット,及び一般)
- 単純Well-Structuredワークフローネットの諸性質(グラフ,ペトリネット,ニューラルネット,及び一般)
- Acyclic Well-Structuredワークフローネットの可達性判定について(グラフ,ペトリネット,ニューラルネット,及び一般)
- Acyclic Well-Structuredワークフローネットの可達性判定について(グラフ,ペトリネット,ニューラルネット,及び一般)
- 拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について
- 拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について
- CPN Toolsによるシングルカーマルチシャフトエレベータシステムのモデル化法と検査への応用
- C言語からペトリネットマークアップ言語への変換ツールC2PNMLとその応用例
- Acyclic Well-Structuredワークフローネットの拡張とその健全性について(グラフ、ペトリネット、ニューラルネット及び一般)
- Acyclic Well-Structuredワークフローネットの拡張とその健全性について(グラフ、ペトリネット、ニューラルネット及び一般)