权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Studies on Computational Complexity/Load as a Metric for the Economy Principles in the Theory of Generative Grammar

生成语法理论中计算复杂性/负载作为经济原理度量的研究

基本信息

批准号：
14510626
负责人：
TOYOSHIMA Takashi
金额：
$ 1.73万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2005
项目状态：
已结题

项目摘要

Possibilities are investigated of the application of the computational complexity theory and the descriptive complexity theory in computer science and discrete mathematics, as the metric for the economy principles in the Minimalist Program, the current theoretical framework in the tradition of transformational generative grammar.In order to measure the complexity of computational operations in human language, the nature of the operations itself needs to be determined, and the problematic head-to-head movement can be, and by the minimalist assumption, must be reformulated as head-to-spec movement, which yields better empirical coverage of phenomena noticed, but left unaccounted for in principled terms.By reducing all the movement operations to just one that moves to a specifier position, it can be considered to be a species of the Merge operation. Then, in turn, we can begin to consider the computational complexity of the economy principles that employ just the two types of the Merge operation, Internal Merge and External Merge.The economy principles in the Minimalist Program can be divided into two types, Derivational Economy and Representational Economy, both of which can be understood as discrete optimization problems. Once so understood, the issues of derivational economy become not of an either-or questions between local vs. global as often alluded in the literature, but rather whether local constraints can solve the global optimization problems, which is the nature of derivational system of human language.It has been found that the notion of locality must be distinguished for derivational economy and representational economy, and the computational one-step "look-ahead" is essential for human language, contra commonly held views. What must be avoided is "look-far-ahead" of more than one step in computation, which inevitably ends up with combinatorial explosion of exponential order.

研究了在计算机科学和离散数学中应用计算复杂性理论和描述复杂性理论作为最简方案中经济原则的度量的可能性，最简方案是转换生成语法传统中的当前理论框架。为了测量人类语言中计算操作的复杂性，需要确定操作本身的性质，并且有问题的头部到头部的运动可以被重新表示为并且根据最小假设，必须被重新表示为头部到规格的运动，这产生了对所注意到的现象的更好的经验性覆盖，通过将所有移动操作减少到仅一个移动到说明符位置的操作，它可以被认为是合并操作的一种。然后，我们可以开始考虑只采用内部合并和外部合并这两种类型的合并操作的经济原则的计算复杂性。最简方案中的经济原则可以分为两种类型，派生经济和代表性经济，这两种经济原则都可以理解为离散优化问题。一旦这样理解，派生经济问题就不再是文献中经常提到的局部与全局的非此即彼的问题，而是局部约束能否解决全局优化问题，这是人类语言派生系统的本质。人们发现，派生经济和代表性经济必须区分局部性的概念，而计算性的一步向前看是人类语言所必需的，这与人们普遍认为的观点相反。必须避免的是计算中不止一步的“前瞻”，这不可避免地以指数级的组合爆炸告终。