Reduction from CFG Parsing to BMM

FROM: CFG Parsing TO: BMM

Implications

if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix
then: from-time: $O(gn^{3-\epsilon})$ where $g$ is the size of the CFG

Year

1975

Reference

L. G. Valiant. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10 (1975), 308–315.

https://www.sciencedirect.com/science/article/pii/S0022000075800468