Feb, 2017

CCG 解析的复杂性

TL;DR本研究研究了 Vijay-Shanker 和 Weir(1994)形式主义下组合范畴语法(CCG)的解析复杂性。我们的主要结果是,在分析中,将语法的大小(而不仅仅是输入句子的长度)考虑进去时,该形式主义的任何解析算法最坏情况下需要指数时间。这与弱等价形式主义(如 Tree-Adjoining Grammar (TAG))有所不同,对于这种形式主义,可以在与语法和输入句子的大小成多项式时间完成分析。我们的研究结果有助于更加深入地理解轻度上下文敏感语法的分类,并为寻找新的轻度上下文敏感版本的 CCG 提供信息。