Fast context-free grammar parsing requires fast boolean matrix multiplication

ABSTRACT

In 1975, Valiant showed that Boolean matrix multiplication can be used for parsing context-free grammars (CFGs), yielding the asympotically fastest (although not practical) CFG parsing algorithm known. We prove a dual result: any CFG parser with time complexity O(gn^3-∈), where g is the size of the grammar and n is the length of the input string, can be efficiently converted into an algorithm to multiply m × m Boolean matrices in time O(m^3-∈/3). Given that practical, substantially subcubic Boolean matrix multiplication algorithms have been quite difficult to find, we thus explain why there has been little progress in developing practical, substantially subcubic general CFG parsers. In proving this result, we also develop a formalization of the notion of parsing.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: ARLAZAROV, V. L., DINIC, E. A., KRONROD, M. A., AND FARADZEV, I. A. 1970. On economical construction of the transitive closure of an oriented graph. Soviet Math. Dokl. 11, 1209-1210. (English translation of Russian article in Dokl. Akad. Nauk SSSR 194 (1970).)
• 3: David H. Bailey, Extra high speed matrix multiplication on the Cray-2, SIAM Journal on Scientific and Statistical Computing, v.9 n.3, p.603-607, May 1988 [doi>10.1137/0909040]
• 4: CHOMSKY, N. 1956. Three models for the description of language. IRE Trans. Inf. Theory 2, 3, 113-124.
• 5: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 6: Don Coppersmith , Shmuel Winograd, Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation, v.9 n.3, p.251-280, March 1990 [doi>10.1016/S0747-7171(08)80013-2]
• 7: DURBIN, R., EDDY, S., KROGH, A., AND MITCHISON, G. 1998. Biological Sequence Analysis. Cambridge University Press, Cambridge, Mass.
• 8: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 9: GALLAIRE, H. 1969. Recognition time of context-free languages by on-line Turing machines. Inf. Cont. 15, 3 (Sept.), 288-295.
• 10: Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980 [doi>10.1145/357103.357112]
• 11: Ivan M. Havel , Michael A. Harrison, On the Parsing of Deterministic Languages, Journal of the ACM (JACM), v.21 n.4, p.525-548, Oct. 1974 [doi>10.1145/321850.321851]
• 12: M.A. A. Harrison , M. A. Harrison, Introduction to Formal Language Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1978
• 13: HARTMANIS, J., AND STEARNS, R. E. 1965. On the computational complexity of algorithms. Trans. AMS 117, 285-306.
• 14: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: Mark Johnson, PCFG models of linguistic tree representations, Computational Linguistics, v.24 n.4, p.613-632, December 1998
• 16: Aravind Joshi, Parsing techniques, Survey of the state of the art in human language technology, Cambridge University Press, New York, NY, 1997
• 17: JOSHI, A. K., LEVY, L. S., AND TAKAHASHI, M. 1975. Tree adjunct grammars. J. Comput. Syst. Sci. 10, 1, 136-163.
• 18: Daniel Jurafsky , James H. Martin, Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, Prentice Hall PTR, Upper Saddle River, NJ, 2000
• 19: KASAMI, T. 1965. An efficient recognition and syntax algorithm for context-free languages. Scientific Rep. AFCRL-65-758. Air Force Cambridge Research Lab, Bedford, Mass.
• 20: Mark-Jan Nederhof , Giorgio Satta, Efficient tabular LR parsing, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.239-246, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981895]
• 21: Sanguthevar Rajasekaran , Shibu Yooseph, TAL recognition in O(M(n2)) time, Journal of Computer and System Sciences, v.56 n.1, p.83-89, Feb. 1998 [doi>10.1006/jcss.1997.1537]
• 22: Walter L. Ruzzo, On the Complexity of General Context-Free Language Parsing and Recognition (Extended Abstract), Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.489-497, July 16-20, 1979
• 23: Wojciech Rytter, Fast recognition of pushdown automaton and context-free languages, Information and Control, v.67 n.1-3, p.12-22, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80024-3]
• 24: Wojciech Rytter, Context-free recognition via shortest paths computation: a version of Valiant's algorithm, Theoretical Computer Science, v.143 n.2, p.343-352, June 12, 1995 [doi>10.1016/0304-3975(94)00265-K]
• 25: Giorgio Satta, Tree-adjoining grammar parsing and boolean matrix multiplication, Computational Linguistics, v.20 n.2, p.173-191, June 1994
• 26: Joel I Seiferas, A simplified lower bound for context-free-language recognition, Information and Control, v.69 n.1-3, p.255-260, April/May/June 1986 [doi>10.1016/S0019-9958(86)80048-1]
• 27: STRASSEN, V. 1969. Gaussian elimination is not optimal. Num. Math. 14, 3, 354-356.
• 28: Volker Strassen, Algebraic complexity theory, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 29: Mithuna Thottethodi , Siddhartha Chatterjee , Alvin R. Lebeck, Tuning Strassen's matrix multiplication for memory efficiency, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-14, November 07-13, 1998, San Jose, CA
• 30: VALIANT, L. G. 1975. General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10, 308-315.
• 31: YOUNGER, D. H. 1967. Recognition and parsing of context-free languages in time n 3 . Inf. Cont. 10, 2, 189-208.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Language parsing and understanding

General Terms:
Algorithms, Theory

Keywords:
Boolean matrix multiplication, context-free grammar parsing