Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication

Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication Lillian Lee Division of Engineering and Applied Sciences Harvard University 33 Oxford Street Cambridge, MA 012138 llee~eecs, harvard, edu Abstract 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. 1 Introduction The context-free grammar (CFG) formalism was developed during the birth of the field of computational linguistics. The standard meth- ods for CFG parsing are the CKY algorithm (Kasami, 1965; Younger, 1967) and Earley's al- gorithm (Earley, 1970), both of which have a worst-case running time of O(gN 3) for a CFG (in Chomsky normal form) of size g and a string of length N. Graham et al. (1980) give a vari- ant of Earley's algorithm which runs in time O(gN3/log N). Valiant's parsing method is the asymptotically fastest known (Valiant, 1975). It uses Boolean matrix multiplication (BMM) to speed up the dynamic programming in the CKY algorithm: its worst-case running time is O(gM(N)), where M(rn) is the time it takes to multiply two m x m Boolean matrices together. The standard method for multiplying ma- trices takes time O(m3). There exist matrix multiplication algorithms with time complexity O(m3-J); for instance, Strassen's has a worst- case running time of O(m 2"sl) (Strassen, 1969), and the fastest currently known has a worst-case running time of O(m 2"376) (Coppersmith and Winograd, 1990). Unfortunately, the constants involved are so large that these fast algorithms (with the possible exception of Strassen's) can- not be used in practice. As matrix multi- plication is a very well-studied problem (see Strassen's historical account (Strassen, 1990, section 10)), it is highly unlikely that simple, practical fast matrix multiplication algorithms exist. Since the best BMM algorithms all rely on general matrix multiplication 1, it is widely believed that there are no practical O(m 3-~) BMM algorithms. One might therefore hope to find a way to speed up CFG parsing without relying on matrix multiplication. However, we show in this paper that fast CFG parsing requires fast Boolean matrix multiplication in a precise sense: any parser running in time O(gN 3-e) that represents parse data in a retrieval-efficient way can be converted with little computational overhead into a O(m 3-e/3) BMM algorithm. Since it is very improbable that practical fast matrix multiplication algorithms exist, we thus establish one of the first nontrivial limitations on practical CFG parsing. 1The "four Russians" algorithm (Arlazarov et al., 1970), the fastest BMM algorithm that does not sim- ply use ordinary matrix multiplication, has worst-case running time O(mS/log …

Content truncated to 500 words