多重文脈自由言語の所属問題を解く時間的効率のよいアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
自然言語の構文記述向き形式文法として,文脈自由文法の基本的な性質を受け継ぐと共に,生成能力が文脈自由文法より真に大きく,文脈規定文法より真に小さい多重文脈自由文法(mcfg)が提案されている。 mcfgでは,respectivrly構文や倒置文のような,互いに割り込んだ構文を自然に記述できる。さらに,mcfg G,入力長nに対して,時間計算量がO(n^e)である認識アルゴリズムが提案されている。ここで,eはGのみに依存して決まる自由度と呼ばれる定数である。これに対して本論文では,論理行列の積を利用したO(n^<e'-0.624i'+1>)時間のアルゴリズムを提案する。ここでe',i'はGのみに依存して決まる定数である(e'≦e, i'≧1)。
- 社団法人電子情報通信学会の論文
- 1995-12-15
著者
関連論文
- VAR-CCGの生成能力について
- 語彙機能文法のいくつかの部分クラスに対する一般認識問題の計算量について
- 多重文脈自由文法の認識問題について
- 多重文脈自由文法の所属問題に対する並列アルゴリズム(計算および計算量理論とその周辺)
- 多重文脈自由文法のある部分クラスに対する効率の良い構文解析法について
- データマイニングにおける相関規則を求める問題に関する研究
- COMP2000-29 稀出集合問題の計算複雑さ及び連想規則問題との関連
- 頻出集合から連想規則を生成するインクリメンタルアルゴリズム
- 頻出集合からの連想規則の生成の計算複雑さ
- データベースの周期性を判定するアルゴリズム
- 強結合集合問題の計算複雑さ
- 頻出集合のインクリメンタルなデータマイニング
- 効率良く頻出集合をデータマイニング可能なデータベースクラスについて
- データマイニングに要する計算量に関する一考察
- データマイニングにおける頻出集合問題の計算複雑さ
- 並列多重文脈自由言語の時間的効率のよい認識アルゴリズム
- NC-JFGの拡張可能性
- 多重文脈自由言語の所属問題を解く時間的効率のよいアルゴリズム
- 木記憶を持つ木オートマトン
- 木記憶を持つ木オートマトン