Reduction from CFG Parsing to BMM
Revision as of 11:55, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: CFG Parsing TO: BMM == Description == == Implications == if: to-time: $O(n^{3-\epsilon})$ for some $\epsilon > {0}$ where $n \times n$ matrix<br/>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")
FROM: CFG Parsing TO: BMM
Description
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