Parsing by matrix multiplication generalized to Boolean grammars

Research output

23 Citations (Scopus)

Abstract

The well-known parsing algorithm for context-free grammars due to Valiant (1975) [25] is analyzed and extended to handle the more general Boolean grammars, which are context-free grammars augmented with conjunction and negation operators in the rules. The algorithm reduces construction of a parsing table to computing multiple products of Boolean matrices of various sizes. Its time complexity on an input string of length n is O(BMM(n)logn), where BMM(n) is the number of operations needed to multiply two Boolean matrices of size n×n, which is O() with ω<2.373 as per the current knowledge. A parse tree can be constructed in time MM(n)logO( 1)n (where MM(n) is the complexity of multiplying two integer matrices), by applying a known efficient procedure for determining witnesses for Boolean matrix multiplication. The algorithm has a succinct proof of correctness and is ready to be implemented.

Original languageEnglish
Pages (from-to)101-120
Number of pages20
JournalTheoretical Computer Science
Volume516
DOIs
Publication statusPublished - 9 Jan 2014

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parsing by matrix multiplication generalized to Boolean grammars'. Together they form a unique fingerprint.

Cite this