文章基本信息

标题：Splittability of Bilexical Context-Free Grammars is Undecidable
本地全文：下载
作者：Mark-Jan Nederhof ; Giorgio Satta
期刊名称：Computational Linguistics
印刷版ISSN：0891-2017
电子版ISSN：1530-9312
出版年度：2011
卷号：37
期号：4
页码：867-879
DOI：10.1162/COLI_a_00079
语种：English
出版社：MIT Press
摘要：Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(∣w∣⁴), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotically improved to O(∣w∣³). Testing this property is therefore of central interest to parsing efficiency. In this article, however, we show the negative result that splittability of 2-LCFGs is undecidable.