# Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication

Preprint · Lillian Lee

- Archive id: arxiv:cs/0112018
- Published: 2001-12-15
- Venue: Journal of the ACM 49(1), pp. 1--15, January 2002
- arXiv: https://arxiv.org/abs/cs/0112018
- Source URL: https://arxiv.org/abs/cs/0112018
- PDF: https://arxiv.org/pdf/cs/0112018
- Provenance: arxiv

## 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(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.