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 nxn, which is O(n^@w) with @w<2.373 as per the current knowledge. A parse tree can be constructed in time MM(n)log^O^(^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.
['Alexander Okhotin']
Parsing by matrix multiplication generalized to Boolean grammars