プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
本稿はプログラムネットの不活性左議論する.まずプログラムネットの不活性の定義を与える.プログラムネットは任意の発火系列で発火可能にできないノードを持つとき,部分的不活性であると言う.我々は不活性問題を,与えられたプログラムネットが部分的不活性であるかどうかを判定する問題と定義する.我々はプログラムネットを4つのクラスに分類する:一般ネット,非循環ネット,SWITCH-lessネット,非循環SWITCH-lessネット.それから,各クラスに対して不活性問題の判定法を議論する.以下の結果が得られた:(1)非循環SWITCH-lessネットは部分的不活性ではない.(2)SWITCH-lessネットに対しては,不活性問題は多項式時間で解くことができる.(3)非循環ネットおよび一般ネットに対しては,不活性問題はおそらくNPに含まれないと考えられる.
- 2004-10-28
著者
-
山口 真悟
山口大学大学院理工学研究科
-
田中 稔
山口大学大学院理工学研究科
-
葛 崎偉
山口大学教育学部
-
田中 稔
山口大学工学部知能情報システム工学科
-
山口 真悟
山口大学工学部
-
山田 紘輔
山口大学大学院理工学研究科
-
葛 崎偉
広島大学工学部
関連論文
- 自由選択ワークフローネットのWell-Structuredワークフローネットへのリファクタリングについて
- 自由選択ワークフローネットのWell-Structuredワークフローネットへのリファクタリングについて
- A-12-1 Well-Structuredワークフローネットへのリファクタリングの提案(A-12.コンカレント工学,一般セッション)
- アクションを共有するワークフローネットに対する振る舞い継承と健全性を満たす合成規則(ペトリネット,離散事象システム,一般)
- ワークフローネットの健全性判定に対するモデル検査法について
- トークン分布に依存した停止性のSWITCH-lessネットに対する判定について(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- 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.基礎・境界分野の研究最前線,ソサイエティ特別企画,ソサイエティ企画)
- デバイスドライバのアクティビティ図に対するペトリネットに基づく検査について(ハイブリッドシステム,コンカレント工学一般)
- WFネットの健全化問題の提案とProtocol継承を考慮した部分問題に対する一考察(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- CSTソリューションコンペティション2007 : 評価実験の詳細報告(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- AI-1-5 CSTソリューションコンペティション2007(総括)(AI-1. CSTソリューションコンペティション2007:表彰式・シンポジウム,依頼シンポジウム,ソサイエティ企画)
- A-12-1 デバイスドライバのアクティビティ図を検査するためのペトリネットに基づく手法の提案(A-12. コンカレント工学,一般セッション)
- Well-Structuredワークフローネットの並列度を計算するための最長パスに着目したヒューリスティックアルゴリズム(グラフ,ペトリネット,ニューラルネット及び一般)
- モデル検査ツールSPINによるワークフローネットの健全性の判定について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- D-3-2 割り込みシステムに対するモデル検査ツールSPINを用いたハングアップの検証(D-3.ソフトウェアサイエンス,一般講演)
- A-12-5 モデル検査ツールSPINによるacyclic ACWFネットの健全性の検証について(A-12.コンカレント工学,一般講演)
- 割り込み処理のDelegationに基づく設計方法およびモデル検査方法について
- AS-3-4 CSTソリューションコンペティション2010の概要 : マルチカーエレベータの最適制御(AS-3.コンカレントシステム理論の最近の発展とその応用,シンポジウムセッション)
- ホモグラフィから生ずる画像歪みに着目したタッチスクリーンの実現(一般セッション(2),パターン認識・メディア理解のための学習理論とその応用)
- 健全性と振る舞い継承を維持するワークフローネットの並列合成について(システムと信号処理及び一般)
- 健全性と振る舞い継承を維持するワークフローネットの並列合成について(システムと信号処理及び一般)
- CAS2010-11 健全性と振る舞い継承を維持するワークフローネットの並列合成について(システムと信号処理及び一般)
- 健全性と振る舞い継承を維持するワークフローネットの並列合成について(システムと信号処理及び一般)
- A-12-8 CSTソリューションコンペティション2007 : 課題と評価ツール(A-12.コンカレント工学,一般講演)
- AP-2-5 CSTソリューションコンペティション2007(概要)(AP-2.コンカレント技術研究の方向性,パネル討論,ソサイエティ企画)
- A-12-4 デバイスドライバのネット指向テーラーメイド設計システムの提案(A-12.コンカレント工学,一般セッション)
- AI-2-3 反転時間とカゴの運転効率を重視したマルチカーエレベータの制御アルゴリズムの提案(AI-2.CSTソリューションコンペティション2008:表彰式・シンポジウム,ソサイエティ企画)
- 不活性なトランジションを持つワークフローネットのProtocol継承を考慮した健全化について(グラフ,ペトリネット,ニューラルネット,及び一般)
- Well-Structuredワークフローネットの並列度を計算するための最長パスに着目したヒューリスティックアルゴリズム(グラフ,ペトリネット,ニューラルネット及び一般)
- 携帯電話のQRコードリーダー機能を用いた出席システム(e-LearningとFD支援/一般)
- Acyclic拡張自由選択ワークフローネットに対する直列化可能性のリファクタリングによる判定方法の提案(一般)
- CSTソリューションコンペティション2007 : 評価ツールの詳細(グラフ,ペトリネット,ニューラルネット及び一般)
- CSTソリューションコンペティション2007 : 評価ツールの詳細(グラフ,ペトリネット,ニューラルネット及び一般)
- 4)組織構造に基づく対話型ワークフロー管理方式(ネットワーク映像メディア研究会)
- 組織構造に基づく対話型ワークフロー管理方式
- 組織構造に基づく対話型ワークフロー管理方式
- 2)スケールスペース解析によるカラーテクスチュア画像の構造記述(ヒューマンインフォメーション研究会)
- アイコン共有機構を備えたマルチユーザアイコニックシステム
- 確率過程に基づくアイコンの呈示
- シグナル伝達経路ペトリネットモデルにおける遅延時間の整合性確認手法の提案 (コンカレント工学)
- A-12-3 抑止アーク付きワークフローネットに対する健全性判定の一考察(A-12.コンカレント工学,一般セッション)
- 抑止アーク付きワークフローネットに対する健全性判定について(グラフ,ペトリネット,ニューラルネット及び一般)
- 抑止アーク付きワークフローネットに対する健全性判定について(グラフ,べトリネット,ニューラルネット及び一般)
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic Well-StructuredデータフロープログラムネットのMaxPARAdegの近似計算について(コンカレントシステム, 一般)
- SWITCH-nodeを持つデータフロープログラムネットの並列度の計算について(コンカレントシステム, 一般)
- プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
- 競合なしリソース付きwell-structuredワークフローネットの最大スループットの計算について(グラフ,ペトリ,ニューラルネット及び一般)
- 状態機械ワークフローネットのAbort型動的変更に対する最悪変更時間の計算複雑さと性能解析について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 状態機械ワークフローネットのFlush、Abort、SCO方式による動的変更に対する最悪変更時間の計算について(コンカレントシステム, 一般)
- A-12-4 並行同期型のインターワークフローの振る舞い継承について(A-12.コンカレント工学,一般講演)
- A-12-3 LPによる初等T-invariantのサポートベクトルの実用的な計算について(A-12.コンカレント工学,一般講演)
- well-structured WFネットの構造解析とPARAdegの近似計算について(コンカレントシステム,一般)
- インターワークフローのラベル付きWFネットモデルと振る舞い継承について (第20回 回路とシステム軽井沢ワークショップ論文集) -- (形式的手法)
- D-3-4 delegationイベントモデルに基づく割り込み処理のUMLモデリング(D-3.ソフトウェアサイエンス,一般講演)
- ワークフローネットの健全性と並列度について(コンカレントシステム, 一般)
- インターワークフローのワークフローネットモデルとその健全性について (形式的手法)
- 複数のCPUボードを用いたシステムの実行時間と稼働率を見積り可能なビジュアルプログラミングシステムの開発
- A-12-10 C言語からペトリネットマークアップ言語への変換ツール : C2PNMLの提案(A-12.コンカレント工学,一般セッション)
- CSTソリューションコンペティション2010 : マルチカーエレベータの最適制御(CSTソリューションコンペティション2010,コンカレントシステム及び一般)
- ワークフローネットの合成規則の結合性とその応用について(一般,コンカレントシステム及び一般)
- シグナル伝達経路ペトリネットモデルにおける遅延時間の整合性確認手法の提案(一般,コンカレントシステム及び一般)
- 並行同期型インターワークフローの振舞い継承に対する健全性に基づく多項式時間判定について(一般,コンカレントシステム及び一般)
- AS-3-6 ワークフローネットの解析問題と解析能力(AS-3.ワークフローとビジネスプロセス管理への数理的アプローチ,シンポジウムセッション)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- Acyclic拡張自由選択ワークフローネットからAcyclic Well-Structuredワークフローネットヘリファクタリングするための条件について(システムと信号処理及び一般)
- A-12-2 時間ペトリネットから時間オートマトンへのコンパクトな変換について(A-12.システム数理と応用,一般セッション)
- 単純Well-Structuredワークフローネットの諸性質(グラフ,ペトリネット,ニューラルネット,及び一般)
- 単純Well-Structuredワークフローネットの諸性質(グラフ,ペトリネット,ニューラルネット,及び一般)
- Acyclic Well-Structuredワークフローネットの可達性判定について(グラフ,ペトリネット,ニューラルネット,及び一般)
- Acyclic Well-Structuredワークフローネットの可達性判定について(グラフ,ペトリネット,ニューラルネット,及び一般)
- 拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について
- 拡張自由選択ワークフローネットとそのサブネット間のProtocol継承の多項式時間判定について
- 拡張自由選択ワークフローネットとそのサブネット間の Protocol 継承の多項式時間判定について
- Acyclic Well-Structured ワークフローネットの可達性判定について
- 単純 Well-Structured ワークフローネットの諸性質
- Acyclic Well-Structured ワークフローネットの可達性判定について
- 単純 Well-Structured ワークフローネットの諸性質
- CPN Toolsによるシングルカーマルチシャフトエレベータシステムのモデル化法と検査への応用
- C言語からペトリネットマークアップ言語への変換ツールC2PNMLとその応用例
- 拡張自由選択ワークフローネットとそのサブネット間の Protocol 継承の多項式時間判定について
- A-12-5 ペトリネットの状態数計算問題の一考察(A-12.システム数理と応用,一般セッション)
- 山口大学における産学連携によるIT人材基礎力養成講座
- Acyclic Well-Structuredワークフローネットの拡張とその健全性について(グラフ、ペトリネット、ニューラルネット及び一般)
- Acyclic Well-Structuredワークフローネットの拡張とその健全性について(グラフ、ペトリネット、ニューラルネット及び一般)
- 自由選択ワークフローネットにおける非安全マーキングへの可達性解析
- A-12-5 Well-Structuredワークフローネットの振舞いの分割可能性について(A-12.システム数理と応用,一般セッション)
- AP-1-4 ワークフローライフサイクルマネジメントへのペトリネットに基づくアプローチ(AP-1.サイバーフィジカルシステムにおけるモデリング手法,パネルセッション,ソサイエティ企画)
- CPN Tools によるシングルカーマルチシャフトエレベータシステムのモデル化法と検査への応用
- 健全なサイクリックWell-Structuredワークフローネットの可達性の多項式時間判定について