Paper: Worst-Case Synchronous Grammar Rules

ACL ID N07-1019
Title Worst-Case Synchronous Grammar Rules
Venue Human Language Technologies
Session Main Conference
Year 2007

We relate the problem of finding the best application of a Synchronous Context- Free Grammar (SCFG) rule during pars- ing to a Markov Random Field. This representation allows us to use the the- ory of expander graphs to show that the complexity of SCFG parsing of an input sentence of length N is Ω(Ncn), for a grammar with maximum rule length n and some constant c. This improves on the previous best result of Ω(Nc√n).