### Fast context-free grammar parsing requires fast boolean matrix multiplicationFast context-free grammar parsing requires fast boolean matrix multiplication

Access Restriction
Subscribed

 Author Lee, Lillian Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2002 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Boolean matrix multiplication ♦ Context-free grammar parsing Abstract In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time complexity $O(gn^{3-∈}),$ where $\textit{g}$ is the size of the grammar and $\textit{n}$ is the length of the input string, can be efficiently converted into an algorithm to multiply $\textit{m}$ × $\textit{m}$ Boolean matrices in time $O(m^{3-∈/3}).$ Given that practical, substantially subcubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially subcubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2002-01-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 49 Issue Number 1 Page Count 15 Starting Page 1 Ending Page 15

#### Open content in new tab

Source: ACM Digital Library