Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication
| dc.creator | Lee, Lillian | |
| dc.date | 1997-08-14 | |
| dc.date.accessioned | 2026-07-07T09:10:57Z | |
| dc.date.available | 2026-07-07T09:10:57Z | |
| dc.description | Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual result: CFG parsers running in time $O(|G||w|^{3 - \myeps})$ on a grammar $G$ and a string $w$ can be used to multiply $m \times m$ Boolean matrices in time $O(m^{3 - \myeps/3})$. In the process we also provide a formal definition of parsing motivated by an informal notion due to Lang. Our result establishes one of the first limitations on general CFG parsing: a fast, practical CFG parser would yield a fast, practical BMM algorithm, which is not believed to exist. | |
| dc.description | 6 pages, uses aclap.sty and eepic.sty | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9708008 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9708008 | |
| dc.identifier | Proceedings of the 35th ACL/8th EACL, pp 9-15 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151513 | |
| dc.subject | Computation and Language | |
| dc.title | Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication | |
| dc.type | text |