Splittability of Bilexical Context-Free Grammars is Undecidable

Abstract

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|^4), where w is the input string.

The split property states that, in a 2-LCFG, the left arguments of
a head are always independent of the right arguments, and vice versa.  When 2-LCFGs have the split property, parsing time can be asymptotically improved to O(|w|^3).  Testing this property is therefore of central interest to parsing efficiency.  However, in this article we show the negative result that the split property of 2-LCFGs is undecidable.