Lee (1997)'s reduction shows that there can be a no O(|G|n 3− ) for some constant > 0 (sub-cubic-time) algorithm for CFG-parsing without implying a significant breakthrough in BMM, which is widely believed not to be possible.
the construction required the grammar size |G| = Θ(n 6 ) to be dependent on the the input size n, which, as Lee (1997) points out, is unrealistic in most applications.