単一パラメータマクロ木変換機とSpine Grammarの関係(<小特集>LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
Spine Grammar[1]は制限された文脈自由木文法[2]であり,自然言語学の分野において広く研究され高速な認識アルゴリズム[3],[4]が知られているTree Adjoining Grammar[5],[6]と同じ文字列言語のクラスを生成することが知られた木文法である.Spine Grammarの生成する木言語のクラスは,非終端記号のランクが1または0であるような文脈自由木文法の生成する木言語のクラスと一致することや,線形・プッシュダウン木オートマトン[1]が受理する木言語のクラスとも一致することが知られている.しかし,木変換機との関連については,まだ研究されていなかった.本研究は,完全決定性・線形・無削除という三つの制限とともに,単一パラメータと呼ぶ制限を満たすマクロ木変換機の生成する表層集合のクラスは,Spine Grammarの生成する木言語のクラスと一致することを証明するものである.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
関連論文
- ラベル選択を有する最小全域木問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 木オートマトンによる無閉路有向グラフの全域木の認識問題
- ユニバーサル・デザインによる視覚障害者用触読図作図システムの開発(ヒューマンコミュニケーショングループ(HCG)シンポジウム)
- 順序機械の多項式時間推論アルゴリズム(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 順序機械の多項式時間推論アルゴリズム
- 線形プッシュダウン・木オートマトン (計算モデルとアルゴリズム)
- 順序機械の多項式時間推論アルゴリズム
- 翻訳過程における木変換機の出力木の変換システム
- 多段階木変換機について(計算モデルと計算の複雑さに関する研究)
- 決定性・線形プッシュダウン木オートマトンによる木構造の線形時間認識
- $O(n^3)$で認識される文脈自由木言語のサブクラスについて (計算機科学基礎理論とその応用)
- 単一パラメータマクロ木変換機とSpine Grammarの関係(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- Spine Grammarの線形性と無削除性
- 木オートマトンを用いた化学グラフのスクリーニング手法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- ラベル選択付最小連結全域部分グラフ問題と化学構造式OCRへの応用 (アルゴリズムと計算理論の新展開)