Parsing and Descriptional Succinctness in Natural Language

计算语言学的摘要研究引入了新的自然语言(NL)的语法形式，它通过使用和操纵复杂的结构，如树和图，获得比上下文无关语法更强的表达能力。有人认为，与不那么强大的语法相比，这些形式主义能够更简洁地描述语言现象。然而，这些形式主义的力量的增强引发了关于它们计算可行性的重要问题。具体地说：(1)对于这些强大的语法，自然语言分析的效率如何？(2)当从较弱的语法转移到更强大的语法可以用精确的数学术语量化吗？计划中的研究旨在解决这两个问题。首先，将推导出分析复杂性的上界，并将针对不同的自然语言语法开发最有效的分析算法，包括串行和并行。其次，将开发一个数学框架来比较不同形式主义的相对简洁性。使用语法大小作为描述复杂性的衡量标准，从弱者转变为强者时简洁性的收益(如果有的话)将被精确地量化。这项研究的结果将有助于评估基于强大的语法形式主义构建自然语言处理系统的实用性。

ABSTRACTS Research in computational linguistics has introduced new grammatical formalisms for natural language (NL) which achieve greater expressive power than context-free grammars through the use and manipulation of complex structures such as trees and graphs. It is argued that these formalisms allow for more succinct descriptions of linguistic phenomena than less powerful grammars. However, the enhanced power of these formalisms raises important questions concerning their computational feasibility. Specifically: (1) How efficient can NL parsing be carried out for these powerful grammars? (2) Can the purported succinctness gain when moving from a weaker to a more powerful grammar be quantified in precise mathematical terms? The planned research is aimed at resolving these two questions. First, upper bounds on the complexity of parsing will be derived, and the most efficient parsing algorithms, both serial and parallel, for different natural language grammars will be developed. Secondly, a mathematical framework for comparing the relative succinctness of different formalisms will be developed. Using grammar size as a measure of descriptional complexity, the gain in succinctness (if any) when moving from a weaker to a more powerful will be quantified precisely. The results of this investigation will be useful in assessing the practicability of building natural language processing systems based on powerful grammatical formalisms.