Lillian Lee.

The journal version of this paper, Fast Context-Free Grammar Parsing
Requires Fast Boolean Matrix Multiplication, was published in the
*Journal of the ACM*; follow the link for the paper, talk
slides, and other information.

*Abstract*: 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.

*Paper formats *:
ps,
pdf,
other

*BibTeX entry*:

@InProceedings{Lee:97a, author = "Lillian Lee", title = "Fast Context-Free Parsing Requires Fast {Boolean} Matrix Multiplication", booktitle = "35th Annual Meeting of the ACL", year = 1997, pages = {9--15} }

Back links: Lillian Lee's home page or papers page; Cornell NLP page.