Parsing by matrix multiplication generalized to Boolean grammars

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(^nω) with ω<2.373 as per the current knowledge. A parse tree can be constructed in time MM(n)logO( ¹⁾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.