Parsing and Descriptional Succinctness in Natural Language

自然语言的解析和描述简洁性

• 批准号: 9022010
• 负责人: Michael Palis
• 金额: $ 1.44万
• 依托单位: University of Pennsylvania
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-09-01 至 1992-07-01
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9022010&HistoricalAwards=false
• 关键词: Parsing; Descriptional; Succinctness; Natural; Language

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.

计算语言学中的摘要研究引入了自然语言（NL）的新语法形式主义（NL），通过使用和操纵复杂的结构（例如树木和图形），它们比无上下文的语法具有更大的表达能力。 有人认为，这些形式主义允许对语言现象的更简洁的描述，而不是强大的语法。 但是，这些形式主义的增强力量提出了有关其计算可行性的重要问题。 具体来说：（1）这些强大的语法如何进行NL解析效率？ （2）用精确的数学术语量化从弱弱到更强大的语法时，所谓的简洁性可以获得吗？ 计划的研究旨在解决这两个问题。 首先，将得出有关解析复杂性的上限，并且将开发出最有效的解析算法，包括串行和平行，对于不同的自然语言语法。 其次，将开发用于比较不同形式主义的相对简洁性的数学框架。 使用语法大小作为描述复杂性的度量，从弱弱到更强大的迁移时，简洁的增益（如果有）将被精确量化。 这项调查的结果将有助于评估基于强大的语法形式主义建立自然语言处理系统的实用性。