Paper: Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication

ACL ID P97-1002
Title Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1997
Authors

Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual re- sult: CFG parsers running in time O([Gl[w[ 3-e) on a grammar G and a string w can be used to multiply m x m Boolean matrices in time O(m3-e/3). In the process we also provide a formal definition of parsing motivated by an informal notion due to Lang. Our re- sult establishes one of the first limita- tions on general CFG parsing: a fast, practical CFG parser would yield a fast, practical BMM algorithm, which is not believed to exist.