Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication
| dc.creator | Lee, Lillian | |
| dc.date | 2001-12-15 | |
| dc.date.accessioned | 2026-07-07T06:32:46Z | |
| dc.date.available | 2026-07-07T06:32:46Z | |
| dc.description | 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(g n^{3 - \epsilson})$, where $g$ is the size of the grammar and $n$ is the length of the input string, can be efficiently converted into an algorithm to multiply $m \times m$ Boolean matrices in time $O(m^{3 - ε/3})$. Given that practical, substantially sub-cubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially sub-cubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing. | |
| dc.description | To appear in Journal of the ACM | |
| dc.identifier | https://arxiv.org/abs/cs/0112018 | |
| dc.identifier | http://arxiv.org/abs/cs/0112018 | |
| dc.identifier | Journal of the ACM 49(1), pp. 1--15, January 2002 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/98971 | |
| dc.subject | Computation and Language | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | I.2.7; F.2.2 | |
| dc.title | Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication | |
| dc.type | text |