Reduction from BMM to CFG Parsing
Revision as of 10:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: BMM TO: CFG Parsing == Description == == 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<br/>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")
FROM: BMM TO: CFG Parsing
Description
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.