Elamur Research⌕
☰
home / papers / 2001 / Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication

Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication

Summary

The paper explains why, over decades, almost no practical algorithms for parsing context-free grammars (CFG) have appeared that are noticeably faster than cubic time. The classical CKY and Earley algorithms run in O(gn³). The asymptotically fastest known method, proposed by Valiant (1975), itself relies on Boolean matrix multiplication (BMM). Lillian Lee proves the connection in the opposite direction. Any parser that runs in O(gn^(3−ε)) and depends linearly on the grammar size can be converted, without much additional overhead, into a BMM algorithm. For m×m matrices, such an algorithm has complexity O(m^(3−ε/3)). To this end, the author introduces a formal definition of a c-parser. This is an algorithm that builds an oracle which answers in constant time whether a nonterminal can consistently derive a given substring. The reduction encodes the contents of the matrices mainly in the grammar rules. No practical subcubic BMM algorithms have been found to date: the fast methods have constants that are too large. Hence, the result sets a fundamental limit on the speed of CFG parsing, which matters for NLP, speech recognition and bioinformatics.

Key points

  • Main theorem: a parser with complexity O(gn^(3−ε)) yields a BMM algorithm with complexity O(m^(3−ε/3)). The best bound is obtained when the string length is of order m^(1/3).
  • A c-parser is defined via "c-derivations", that is, derivations of substrings that are consistent with some complete parse of the sentence. This class includes CKY, Earley, generalized LR and other tabular parsers.
  • BMM context: the Strassen algorithm has complexity O(m^2.81) but pays off only for matrices larger than ~100. The Coppersmith–Winograd algorithm has complexity O(m^2.376) but is impractical.
  • Earlier reductions are weaker. The methods of Ruzzo (1979) and Harrison–Havel turn even a parser with complexity n^1.5 only into a cubic BMM algorithm. The approach is inspired by the reduction of Satta (1994) for TAG, where parsing usually takes O(gn⁶).
  • The article was published in Journal of the ACM 49(1), 2002. A preliminary version appeared at the 35th ACL conference.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Computing & GPUs

Topics Syntax & grammar formalisms

Cite

Cite as Lillian Lee. 2001. Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication. arXiv:cs/0112018 · Journal of the ACM 49(1), pp. 1–15, January 2002.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.cs/0112018 · arXiv cs/0112018

@misc{lee2001fast,
  title = {{Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication}},
  author = {Lillian Lee},
  year = {2001},
  doi = {10.48550/arxiv.cs/0112018},
  eprint = {cs/0112018},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.cs/0112018}
}

References

31 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques and Tools. Addison-Wesley. find
  2. Arlazarov, V. L., E. A. Dinic, M. A. Kronrod, and I. A. Faradz̆ev. 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). find
  3. Bailey, David. 1988. Extra high speed matrix multiplication on the Cray-2. SIAM Journal on Scientific and Statistical Computing, 9(3):603–607. find
  4. Chomsky, Noam. 1956. Three models for the description of language. IRE Transactions on Information Theory, 2(3):113–124. find
  5. Coppersmith, Don and Shmuel Winograd. 1987. Matrix multiplication via arithmetic progression. In Symposium on the Theory of Computing, pages 1–6. find
  6. Coppersmith, Don and Shmuel Winograd. 1990. Matrix multiplication via arithmetic progression. Journal of Symbolic Computation, 9(3):251–280. Special Issue on Computational Algebraic Complexity. find
  7. Durbin, Richard, Sean Eddy, Anders Krogh, and Graeme Mitchison. 1998. Biological Sequence Analysis. Cambridge University Press. find
  8. Earley, Jay. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–102. find
  9. Gallaire, Hervé. 1969. Recognition time of context-free languages by on-line Turing machines. Information and Control, 15(3):288–295, September. find
  10. Graham, Susan L., Michael A. Harrison, and Walter L. Ruzzo. 1980. An improved context-free recognizer. ACM Transactions on Programming Languages and Systems, 2(3):415–462. find
  11. Harrison, Michael and Ivan Havel. 1974. On the parsing of deterministic languages. Journal of the ACM, 21(4):525–548, October. find
  12. Harrison, Michael A. 1978. Introduction to Formal Language Theory. Addison-Wesley. find
  13. Hartmanis, Juris and Richard E. Stearns. 1965. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285–306. find
  14. Hopcroft, John E. and Jeffrey D. Ullman. 1979. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts. find
  15. Johnson, Mark. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632. our card
  16. Joshi, Aravind. 1997. Parsing techniques. In Ronald Cole, Joseph Mariani, Hans Uszkoreit, Giovanni Battista Varile, Annie Zaenen, Antonio Zampolli, and Victor Zue, editors, Survey of the State of the Art in Human Language Technology, Studies in Natural Language Processing. Cambridge University Press… find
  17. Joshi, Aravind K., Leon S. Levy, and Masako Takahashi. 1975. Tree adjunct grammars. Journal of Computer and System Sciences, 10(1):136–163. find
  18. Jurafsky, Daniel and James H. Martin. 2000. Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition. Prentice Hall series in Artificial Intelligence. Prentice Hall. Contributing writers: Andrew Kehler, Keith Vander Linden, and… find
  19. Kasami, Tadao. 1965. An efficient recognition and syntax algorithm for context-free languages. Scientific Report AFCRL-65-758, Air Force Cambridge Research Lab, Bedford, MA. find
  20. Nederhof, Mark-Jan and Giorgio Satta. 1996. Efficient tabular LR parsing. In 34th Annual Meeting of the ACL, pages 239–246. find
  21. Rajasekaran, Sanguthevar and Shibu Yooseph. 1995. TAL recognition in o(m(n 2 )) time. In 33rd Annual Meeting of the ACL, pages 166–73. find
  22. Ruzzo, Walter L. 1979. On the complexity of general context-free language parsing and recognition. In Sixth Colloquium on Automata, Languages and Programming (ICALP), volume 71 of Lecture Notes in Computer Science, pages 489–497. Springer-Verlag. find
  23. Rytter, Wojciech. 1985. Fast recognition of pushdown automaton and context-free languages. Information and Control, 67:12–22. find
  24. Rytter, Wojciech. 1995. Context-free recognition via shortest paths computation: a version of Valiant’s algorithm. Theoretical Computer Science, 143(2):343–352. find
  25. Satta, Giorgio. 1994. Tree-adjoining grammar parsing and Boolean matrix multiplication. Computational Linguistics, 20(2):173–191, June. find
  26. Seiferas, Joel. 1986. A simplified lower bound for context-free-language recognition. Information and Control, 69:255–260. find
  27. Strassen, Volker. 1969. Gaussian elimination is not optimal. Numerische Mathematik, 14(3):354–356. find
  28. Strassen, Volker. 1990. Algebraic complexity theory. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A. Elsevier Science Publishers, chapter 11, pages 633–672. find
  29. Thottethodi, Mithuna, Siddartha Chatterjee, and Alvin R. Lebeck. 1998. Tuning Strassen’s matrix multiplication for memory efficiency. In SC98: High Performance Networking and Computing Conference. find
  30. Valiant, Leslie G. 1975. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10:308–315. find
  31. Younger, Daniel H. 1967. Recognition and parsing of context-free languages in time n 3 . Information and Control, 10(2):189–208. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lee-2001-fast-context-free-grammar-parsing/