言語生成の動的局所決定性経済性と最適化技法による算定量複雑性の研究

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

これまで、ドイツ語スイス方言等が示す連続交差依存構造は形式言語としては緩文脈依存性を示し、形式文法としては線形指標文法等のクラスで生成可能な事が知られていたが、最近、線形プッシュ・ダウン記憶ルート・トゥ・フロンティア型木オートマトンの受理能力が等価であることが証明された(Fujiyoshi ＆ Kasai 2000)。また、緩文脈依存クラスの木連接文法は決定性チューリング機械で多項式時間内に構文解析できる(Rajasekaran 1996)事が知られている。一方、極小主義プログラムでは一般にボトム・アップ型の統語生成が仮定されており、これはフロンティア・トゥ・ルート型木オートマトンに対応する。しかし、有限状態木オートマトンでは決定性及び非決定性フロンティア・トゥ・ルート型、非決定性ルート・トゥ・フロンティア型の受理能力は等価であるが、決定性ルート・トウ・フロンティア型の受理能力はそれより低い事が知られており、決定性と非決定性の線形プッシュ・ダウン記憶ルート・トゥ・フロンティア型木オートマトンの受理能力が等価であるか否かは判明せず、従って極小主義プログラムでの統語生成の算定量(計算量)が決定性多項式時間クラスに納まるか否かも解明できなかった。これは、極小主義プログラムでは形式文法には想定されていない移動操作が仮定されており、特に主要部移動は、形式文法での終端記号の合成にあたり、等価なモデルにはならないと言う問題が存在し、主要部移動は極小主義プログラム内でも数々の理論的問題を抱えているからであった。これまで全ての移動操作を指定部への移動のみに限定する仮説を提案してきたが、モホーク語等で観察される編入現象が問題となっていた。今年度の研究では、編入現象も指定部への移動として説明可能であることを究明し、他に指定部統一移動仮説の傍証となる現象の記述研究を行った。