ACネットの有界活性問題のNP困難性
スポンサーリンク
概要
- 論文の詳細を見る
ペトリネットはコンカレントシステムのモデルの一つである。活性問題はペトリネットの最も重要な解析問題の一つである。一般のペトリネットの活性問題の計算量は、決定性指数領域困難であることが知られている。ペトリネットのサブクラスの活性問題の計算量については、有界な自由選択(EFC)ネットの活性問題が決定性多項式時間で解けること、非有界EFCネットの活性問題がNP完全であることが知られている。EFCを包含するクラスである非対称選択(AC)ネットについては非有界ACネットの活性問題はNP困難であるが、有界なACネットについては著者らの知る限り、未解決である。本報告は、論理式の充足可能性問題が有界なACネットの活性問題に多項式時間で帰着可能であることから、この問題はNP困難であることが示される。
- 社団法人電子情報通信学会の論文
- 2001-07-17
著者
関連論文
- 色つき量子ペトリネットによる量チューリング機械のモデル化と解析(ペトリネット,離散事象システム,一般)
- 量子ペトリネットによる量子コンピュータのモデル化(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- バッチ処理アークつきマークグラフの可達問題(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 量子ペトリネットを用いた新しい量子コンピュータモデルの提案
- 救急医療システムを対象としたカラーペトリネットシミュレーションモデルの提案と検討 (コンカレント工学)
- Polynomial time solvability of liveness problem of structurally weakly persistent net (コンカレント工学)
- Polynomial time solvability of liveness problem of structurally weakly persistent net (信号処理)
- Polynomial time solvability of liveness problem of structurally weakly persistent net (VLSI設計技術)
- Polynomial time solvability of liveness problem of structurally weakly persistent net (回路とシステム)
- P-インバリアントを用いたペトリネットのフィードバック制御 : 発火不可制御、不可観測なトランジションがある場合
- TCCネットが活性な初期マーキングをもつための条件
- 通信プロトコルのネットモデルとその解析(ハイブリッドシステム,コンカレント工学一般)
- AP-4-2 コンカレント技術研究の現状(AP-4.コンカレント技術の現在・過去・未来,パネル討論,ソサイエティ企画)
- Fourier-Motzkin法を応用したペトリネットの基本サイフォンの列挙(コンカレントシステム, 一般)
- CORBAのコールバック問題のためのペトリネットの構造と解析について(コンカレントシステム, 離散事象システム, ハイブリッドシステム, 及び一般)
- 挙動的トラップのPOCネットの活性の単調性への応用(グラフ,ペトリ,ニューラルネット及び一般)
- ペトリネットを用いたCORBAにおけるコールバック問題の解析(コンカレント工学理論と応用一般)
- バッチ処理アークつきペトリネットのプレースインバリアント(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ペトリネットを用いたCORBAのコールバック問題に対する検討(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)
- ペトリネットのトークン不足サイフォンと活性単調性解析への応用
- バッチ処理アークつきペトリネットの記述能力(グラフ,ペトリ,ニューラルネット,及び一般)
- 量子ペトリネットを用いた新しい量子コンピュータモデルの提案
- A-12-2 ペトリネットの故障診断に関する一考察(A-12.コンカレント工学,一般セッション)
- AT-3-1 ペトリネットとその拡張クラス(AT-3. コンカレント工学の理論と応用,チュートリアルセッション,ソサイエティ企画)
- 挙動的トラップのPOCネットの活性の単調性への応用(グラフ,ペトリ,ニューラルネット及び一般)
- 構造的弱パーシステントネットの活性問題の計算量(システムと信号処理及び一般)
- 救急医療システムを対象としたカラーペトリネットシミュレーションモデルの提案と検討(一般)
- 構造的弱パーシステントネットの活性問題の計算量(システムと信号処理及び一般)
- 構造的弱パーシステントネットの活性問題の計算量(システムと信号処理及び一般)
- CAS2010-23 構造的弱パーシステントネットの活性問題の計算量(システムと信号処理及び一般)
- 空調制御ネットワークにおける自動冷媒系統識別ユニット番号バインディング
- バッチ処理アークつきペトリネットの記述能力(グラフ,ペトリ,ニューラルネット,及び一般)
- 可達集合が半線形集合であるペトリネットのアンフォールディング(コンカレント工学一般)
- P-インバリアントを用いたペトリネットのフィードバック制御 : 発火不可制御、不可観測なトランジションがある場合
- AP-4-7 グローバルコンピューティングシステム指向設計(AP-4.コンカレント技術の現在・過去・未来,パネル討論,ソサイエティ企画)
- ファジーペトリネットの音楽への応用の可能性
- ファジーペトリネットの音楽への応用の可能性
- A-12-9 マークグラフの故障診断に関する一考察(A-12.コンカレント工学,一般セッション)
- AI-1-1 システム数理基礎理論(AI-1.システム数理と応用-CSTからMSSへ-,依頼シンポジウム,ソサイエティ企画)
- トラップ包含閉路ネットの活性問題の計算量
- シャフト間の役割を考慮したマルチカーエレベータの運行制御方式の提案(CSTソリューションコンペティション2010,コンカレントシステム及び一般)
- コンカレント工学研究会の活動を振り返って : 歴代委員長からのメッセージ(一般,コンカレントシステム及び一般)
- A-12-1 共有資源つき時間マークグラフの最大スループットの近似算法
- ペトリネットを用いた並列計算機AP3000のプログラミング支援(コンカレント工学一般)
- A-12-3 制限つきワークフローネットの状態方程式に関する一考察
- 接続行列を用いたペトリネットの活性問題の解析について
- SA-6-7 ペトリネットのインバリアントの近似的列挙法
- A-12-1 拡張状態機械の構造活性について
- コンカレントシステムの新しいモデルとペトリネット
- AC/DCネットの活性問題に関する一考察
- トラップ包含閉路ネットの活性問題の計算量
- ACネットの有界活性問題のNP困難性
- 有界なAC/DCネットの単調活性問題の多項式時間解法
- A-12-5 拡張状態機械の活性について
- 有界なPOCネットの単調活性について
- AS-3-4 抑止アーク付きマークグラフの活性解析とワークフローへの応用(AS-3.ワークフローとビジネスプロセス管理への数理的アプローチ,シンポジウムセッション)
- トラップ包含閉路ネットの検証法(グラフ,ペトリネット,ニューラルネット,及び一般)
- トラップ包含閉路ネットの検証法(グラフ,ペトリネット,ニューラルネット,及び一般)
- トラップ包含閉路ネットの検証法
- トラップ包含閉路ネットの検証法
- システム数理基礎理論
- ペトリネットを用いた量子回路のモデル化と解析