Reduction from BMM to CFG Parsing: Revision history

Jump to navigation Jump to search

Diff selection: Mark the radio buttons of the revisions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with latest revision, (prev) = difference with preceding revision, m = minor edit.

    15 February 2023

    • curprev 10:5510:55, 15 February 2023‎ Admin talk contribs‎ 467 bytes +467‎ 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"
Retrieved from "https://algorithm-wiki.csail.mit.edu/wiki/Reduction_from_BMM_to_CFG_Parsing"