プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
スポンサーリンク
概要
- 論文の詳細を見る
本稿はプログラムネットの不活性左議論する.まずプログラムネットの不活性の定義を与える.プログラムネットは任意の発火系列で発火可能にできないノードを持つとき,部分的不活性であると言う.我々は不活性問題を,与えられたプログラムネットが部分的不活性であるかどうかを判定する問題と定義する.我々はプログラムネットを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.コンカレント工学,一般講演)
- 通信時間を考慮したマルチプロセッサスケジューリング手法の提案(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- マルチプロセッサシステムのための複数の静的優先リストを用いた動的スケジューリング手法の提案(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 割り込み処理のDelegationに基づく設計方法およびモデル検査方法について
- シグナル伝達経路のペトリネット表現に基づく反応パラメータ条件式導出アルゴリズムの提案(システムバイオロジー,システムバイオロジー,一般)
- ホモグラフィから生ずる画像歪みに着目したタッチスクリーンの実現(一般セッション(2),パターン認識・メディア理解のための学習理論とその応用)
- 通信時間を考慮したタスクグラフの最適実行時間の上下界について
- A-12-8 CSTソリューションコンペティション2007 : 課題と評価ツール(A-12.コンカレント工学,一般講演)
- AP-2-5 CSTソリューションコンペティション2007(概要)(AP-2.コンカレント技術研究の方向性,パネル討論,ソサイエティ企画)
- A-12-4 デバイスドライバのネット指向テーラーメイド設計システムの提案(A-12.コンカレント工学,一般セッション)
- A-12-5 公開鍵暗号MEPKCの暗号化システム実現に関する研究(A-12.コンカレント工学,一般セッション)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- T-インバリアントによるシグナル伝達経路の構造表現(グラフ, ペトリ, ニューラルネット及び一般)
- シグナル伝達経路解析のためのペトリネットに基づく形式的表現の提案(コンカレントシステム, 一般)
- AI-2-3 反転時間とカゴの運転効率を重視したマルチカーエレベータの制御アルゴリズムの提案(AI-2.CSTソリューションコンペティション2008:表彰式・シンポジウム,ソサイエティ企画)
- 不活性なトランジションを持つワークフローネットのProtocol継承を考慮した健全化について(グラフ,ペトリネット,ニューラルネット,及び一般)
- Well-Structuredワークフローネットの並列度を計算するための最長パスに着目したヒューリスティックアルゴリズム(グラフ,ペトリネット,ニューラルネット及び一般)
- 3K11 大学授業におけるアクティブラーニングの教育実践(1) : 「アスリートのためのアカデミック・スキルズ」を対象として((課題研究3-2)教育資料・実践(2),教育の原点に光を当てる〜乱流の中の本流を見出す〜)
- 確率を用いたトークン滞留しない時間ペトリネットモデルのトランジション発火時間の決定法
- 遺伝的アルゴリズムによる通信時間を考慮したマルチプロセッサスケジューリング手法の提案(グラフ,ペトリネット,ニューラルネット,及び一般)
- 遺伝的アルゴリズムによる通信時間を考慮したマルチプロセッサスケジューリング手法の提案(グラフ,ペトリネット,ニューラルネット,及び一般)
- モジュール合成を用いたソフトウェア設計における仕様の充足性検証に関する考察(コンカレントシステム, 一般)
- 自動車制御システムにおけるマルチプロセッサスケジューリングについて
- C言語プログラム構造解析によるフローチャートの生成
- 活用事例 Moodleを用いた中国人学習者向けの日本語4級単語学習システムの構築
- 第二言語としての日本語の能力向上を目指したE-Learningシステムの設計(グラフ,ペトリネット,ニューラルネット,及び一般)
- 第二言語としての日本語の能力向上を目指したE-Learningシステムの設計(グラフ,ペトリネット,ニューラルネット,及び一般)
- A-12-2 中国人日本語学習者向けの単語学習ペトリネットモデル(A-12. コンカレント工学,一般セッション)
- PARAdeg Computation and Scheduling of Self-Cleaning SWITCH-less Program Nets
- 携帯電話のQRコードリーダー機能を用いた出席システム(e-LearningとFD支援/一般)
- マルチプロセッサスケジューリングにおけるタスクグラフのブロック分割について(コンカレントシステム,離散事象システム及び一般)
- 同形グラフの節点対応におけるカーネルセットの提案とその性質について(一般)
- Acyclic拡張自由選択ワークフローネットに対する直列化可能性のリファクタリングによる判定方法の提案(一般)
- 階層化ペトリネットによる飲食店業務のワークフローモデリング
- 動的なワークフロー変更のSCO方式に関する性能評価
- カラーペトリネットによるワークフローのモデリングおよび評価
- カラーペトリネットによるワークフローのモデリングおよび評価
- SA-6-3 在宅医療サービスのためのマルチエージェントシステムについて
- 公開鍵暗号MEPKCのためのペトリネットの生成法およびその初等T-invariantの計算法
- 手書き文字認識のための特徴グラフの類似性判定アルゴリズム(グラフ,ペトリネット,ニューラルネット,及び一般)
- 公開鍵暗号MEPKCの鍵生成器として利用するペトリネットの自動生成およびその複雑化(コンカレント工学一般、及び、CSTソリューションコンペティション2007発表会)
- 自動生成されたペトリネットの初等T-invariantの列挙アルゴリズム(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 公開鍵暗号システムMEPKCにおける鍵生成器の作成(コンカレントシステム, 一般)
- 線形計画法を用いた全ての初等T-invariantの求解について(グラフ,ペトリ,ニューラルネット及び一般)
- 線形計画法を用いた全ての初等T-invariantの求解について(グラフ,ペトリ,ニューラルネット及び一般)
- 柔軟なワークフロー動的変更を実現するための変更方式Selective Shiftの提案(コンカレント工学一般)
- 4)組織構造に基づく対話型ワークフロー管理方式(ネットワーク映像メディア研究会)
- 2)スケールスペース解析によるカラーテクスチュア画像の構造記述(ヒューマンインフォメーション研究会)
- 確率過程に基づくアイコンの呈示
- 優先度付き非決定性スーパバイザの存在条件について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- プログラム理解における支援を目的とした学習者モデルの構築
- SA-7-1 状態機械ワークフローネットのFlush方式とAbort方式による動的変更に対する最悪変更時間の計算について(SA-7. 企業・社会活動におけるコンカレント技術)
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic StructuredプログラムネットのPARAdegの評価と応用について(グラフ,ペトリ,ニューラルネット及び一般)
- Acyclic Well-StructuredデータフロープログラムネットのMaxPARAdegの近似計算について(コンカレントシステム, 一般)
- SWITCH-nodeを持つデータフロープログラムネットの並列度の計算について(コンカレントシステム, 一般)
- プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
- プログラムネットの不活性について(グラフ,ペトリ,ニューラルネット及び一般)
- 競合なしリソース付きwell-structuredワークフローネットの最大スループットの計算について(グラフ,ペトリ,ニューラルネット及び一般)
- 競合なしリソース付きwell-structuredワークフローネットの最大スループットの計算について(グラフ,ペトリ,ニューラルネット及び一般)
- 状態機械ワークフローネットのAbort型動的変更に対する最悪変更時間の計算複雑さと性能解析について(コンカレントシステム,離散事象システム,ハイブリッドシステム,及び一般)
- 状態機械ワークフローネットのFlush、Abort、SCO方式による動的変更に対する最悪変更時間の計算について(コンカレントシステム, 一般)
- A-12-4 並行同期型のインターワークフローの振る舞い継承について(A-12.コンカレント工学,一般講演)
- A-12-3 LPによる初等T-invariantのサポートベクトルの実用的な計算について(A-12.コンカレント工学,一般講演)
- well-structured WFネットの構造解析とPARAdegの近似計算について(コンカレントシステム,一般)
- D-3-4 delegationイベントモデルに基づく割り込み処理のUMLモデリング(D-3.ソフトウェアサイエンス,一般講演)
- ワークフローネットの健全性と並列度について(コンカレントシステム, 一般)
- 複数のCPUボードを用いたシステムの実行時間と稼働率を見積り可能なビジュアルプログラミングシステムの開発
- 二次方程式の解法推測に基づく学習支援システムの開発(e-Learningにおける学習評価/一般)
- 興味優先学習支援システムの開発と評価(先進的学習システム/一般)
- 初心者の誤り要因に基づくプログラミング学習支援とその評価
- リソース配置変更によるマークグラフワークフローネットの最大スループットの改善について(コンカレント工学及びハイブリッドダイナミカルシステムの理論と応用,一般)