Reduction from BMM to CFG Parsing

FROM: BMM TO: CFG Parsing

Implications

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

Year

2002

Reference

L. Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1–15.

https://arxiv.org/abs/cs/0112018