tailieunhanh - Báo cáo khoa học: "Fast Context-Free Parsing Requires Fast Boolean Matrix Multiplication"

Valiant showed that Boolean matrix multiplication (BMM) can be used for CFG parsing. We prove a dual result: 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 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. 1 Introduction The standard method. | 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 Abstract Valiant showed that Boolean matrix multiplication BMM can be used for CFG parsing. We prove a dual result CFG parsers running in time 0 G 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 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. 1 Introduction The context-free grammar CFG formalism was developed during the birth of the field of computational linguistics. The standard methods for CFG parsing axe the CKY algorithm Kasami 1965 Younger 1967 and Earley s algorithm Earley 1970 both of which have a worst-case running time of O gN3 for a CFG in Chomsky normal form of size g and a string of length N. Graham et al. 1980 give a variant 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 m is the time it takes to multiply two m X m Boolean matrices together. The standard method for multiplying matrices takes time O m3 . There exist matrix multiplication algorithms with time complexity O m3-Ổ for instance Strassen s has a worstcase running time of G m281 Strassen 1969 and the fastest currently known has a worst-case running time of ơ m2-376 Coppersmith and Winograd 1990 . Unfortunately the constants involved are so large that these fast algorithms with the possible exception of Strassen s cannot be used in practice. As matrix multiplication is a very .