Splittability of bilexical context-free grammars is undecidable

Mark Jan Nederhof, Giorgio Satta

Research output: Contribution to journalArticlepeer-review

3 Downloads (Pure)


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.
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|^3). Testing this propertyis therefore of central interest to parsing efficiency. In this article, however, we show the negative result that splittability of 2-LCFGs is undecidable.
Original languageEnglish
Pages (from-to)867-879
Number of pages13
JournalComputational Linguistics
Issue number4
Early online date28 Nov 2011
Publication statusPublished - Dec 2011


  • Parsing algorithms
  • Natural language processing


Dive into the research topics of 'Splittability of bilexical context-free grammars is undecidable'. Together they form a unique fingerprint.

Cite this