Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time
Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time
复制标题
在多项式时间内推断轻度上下文敏感语言的语法
DOI：
10.1007/11872436_12
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Mike Atamas
中科院分区：
文献类型：
--
作者：
T. Oates;T. Armstrong;Leonor Becerra;Mike Atamas
自然语言包含规则的、上下文无关的和上下文敏感的句法结构，然而这些类型的形式语言中没有一种可以从肯定的例子中识别出来。轻度上下文敏感语言能够表示一些上下文敏感的结构，这些结构在自然语言中最常见，如多重协议，交叉协议和重复。这些语言由于其表达能力而对自然语言应用程序具有吸引力，并且它们不是完全上下文敏感的事实也应该导致计算优势。我们实现了这样的计算优势，提出了第一个多项式时间算法推断简单的外部上下文语法，一类轻度上下文敏感的语法，从正面的例子。
Natural languages contain regular, context-free, and context-sensitive syntactic constructions, yet none of these classes of formal languages can be identified in the limit from positive examples. Mildly context-sensitive languages are able to represent some context-sensitive constructions, those most common in natural languages, such as multiple agreement, crossed agreement, and duplication. These languages are attractive for natural language applications due to their expressiveness, and the fact that they are not fully context-sensitive should lead to computational advantages as well. We realize one such computational advantage by presenting the first polynomial-time algorithm for inferring Simple External Context Grammars, a class of mildly context-sensitive grammars, from positive examples.