This result is intermediate between the O(n 6 ) for binarizable SCFGs, also known as Inversion Transduction Grammars (Wu 1997), and the O(n 10 ) that we would achieve by recognizing the rule in a single deduction step.
gildea andŠtefankovič (2007) use a combinatorial argument to show that as the number of nonterminals r in an SCFg rule grows, the parsing complexity grows as Ω(n cr ) for some constant c. some very difficult permutations exist of all lengths.