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

使用优化技术研究语言生成和计算复杂性的动态局部确定性经济学

基本信息

批准号：
12710285
负责人：
豊島孝之
金额：
$ 1.28万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

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

到目前为止，我们已经知道，德语等瑞士方言所表现出的连续交叉依赖结构，作为形式语言表现出松散的上下文依赖，并且可以在一类形式语法（例如线性索引语法）中生成，但是最近，已经证明线性下推记忆路线前沿树自动机的接受能力是等效的（Fujiyoshi & Kasai 2000）。此外，众所周知，松散上下文相关类的树连接语法可以由确定性图灵机在多项式时间内解析（Rajasekaran 1996）。另一方面，极简主义程序通常假设自下而上的语法生成，这对应于边界到根树自动机。然而，在有限状态树自动机中，确定性和非确定性边界到边界类型和非确定性根到边界类型的接受能力是等效的，但确定性根到边界类型的接受能力为较低是已知的，并且是确定性的。目前尚不清楚非确定性线性下推记忆根到边界树自动机的接受能力是否等效，因此极简程序中句法生成的计算量（计算量）由确定性多项式决定也不清楚他是否适合这个班级。这是因为，极简程序假设了形式语法中未假设的移动操作，并且特别存在一个问题，即在形式语法中构成终端符号时，主要部分的移动不会产生等效模型。即使在极简主义计划中，主要部分也存在许多理论问题。到目前为止，我们提出了一个假设，将所有移动操作限制为仅移动到指定部分，但在莫霍克等语言中观察到的合并现象已成为一个问题。在今年的研究中，我们发现调动现象也可以解释为向指定部门的流动，并且我们还对其他现象进行了描述性研究，为统一流动假说提供了支持。