木オートマトンによる無閉路有向グラフの全域木の認識問題
スポンサーリンク
概要
- 論文の詳細を見る
本稿では,木オートマトンによる無閉路有向グラフの全域木の認識問題を考える.無閉路有向グラフが木オートマトンによって受理されることを,その無閉路有向グラフが木オートマトンによって受理される全域木を持つことと定義する.この認識問題がNP完全であることと,直並列グラフに対しては線形時間の認識アルゴリズムが存在することを示す.
- 2009-09-07
著者
関連論文
- ラベル選択を有する最小全域木問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 木オートマトンによる無閉路有向グラフの全域木の認識問題
- ユニバーサル・デザインによる視覚障害者用触読図作図システムの開発(ヒューマンコミュニケーショングループ(HCG)シンポジウム)
- 順序機械の多項式時間推論アルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 順序機械の多項式時間推論アルゴリズム
- 線形プッシュダウン・木オートマトン (計算モデルとアルゴリズム)
- 順序機械の多項式時間推論アルゴリズム
- 翻訳過程における木変換機の出力木の変換システム
- 多段階木変換機について(計算モデルと計算の複雑さに関する研究)
- 決定性・線形プッシュダウン木オートマトンによる木構造の線形時間認識
- $O(n^3)$で認識される文脈自由木言語のサブクラスについて (計算機科学基礎理論とその応用)
- 単一パラメータマクロ木変換機とSpine Grammarの関係(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- Spine Grammarの線形性と無削除性
- 木オートマトンを用いた化学グラフのスクリーニング手法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- ラベル選択付最小連結全域部分グラフ問題と化学構造式OCRへの応用 (アルゴリズムと計算理論の新展開)