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

Talk slides: ps, pdf

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}
}