Worst-Case Synchronous Grammar Rules
Daniel Gildea, Daniel Štefankovič · 2007
We relate the problem of finding the best application of a Synchronous Context-Free Grammar (SCFG) rule during parsing to a Markov Random Field. This representation allows us to use the theory 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 Ω(N c √ n 1