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

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

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.