実用的な構文解析技術と形式言語理論をつなぐ統一的な理論基盤の構築

点击翻译按钮获取中文摘要

昨年度に導入した先読み付き文脈自由文法の意味論には、基本的な文法の変換操作である代入の逆の操作が行えない場合があり、標準形への変換についての議論や認識アルゴリズムの計算量の解析が困難であるという問題があった。本年度はその問題を解決する手法として3値の意味論を用いた定式化を得た。これは、文字列の組から真、偽、未定義への写像である3値の先読み付き言語を考え、それらの間に未定義を最小とする順序を入れ、その順序の下での最小解を考えるというものである。この方法は、プログラムの表示的意味論において標準的な方法であり、論理プログラミングにおいてはFittingの意味論と呼ばれている。3値の意味論によって、全ての文法を扱うことができ、代入の逆の操作を自由に行うことができることが分かった。この新たな意味論の下でも、文脈自由文法と解析表現文法の両者の拡張となること、補集合の閉包性を除く閉包性や決定可能性などの基本的な性質、表現力についての結果が成り立つことを証明した。次に、先読み付き文脈自由文法の認識アルゴリズムに関して、微分による認識アルゴリズムを与え、その計算量の解析を行った。その結果として、そのアルゴリズムは、入力文字列の長さn、先読み付き文脈自由文法の大きさ|G|に対し、時間計算量O(n^3 |G|)、空間計算量O(n^2 |G|)で計算可能であることが分かった。これは文脈自由文法に対して得られている結果と同じであるが、先読みの持つ性質の違いによって証明は少し異なり、また、その性質の違いから行列乗算の計算量であるValiant法は先読み付き文脈自由文法に適用することができないことがわかる。最後に、表現力に関して、先読み付き文脈自由文法でk項間漸化式を模倣する方法を発見し、多項式pに対してp(n)の長さからなる文字列全体を表す言語を記述できるという結果を新たに得た。