TY - JOUR

T1 - Parsing by matrix multiplication generalized to Boolean grammars

AU - Okhotin, Alexander

PY - 2014/1/9

Y1 - 2014/1/9

N2 - 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( 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.

AB - 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( 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.

KW - Boolean grammars

KW - Conjunctive grammars

KW - Context-free grammars

KW - Matrix multiplication

KW - Parsing

UR - http://www.scopus.com/inward/record.url?scp=84890553119&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2013.09.011

DO - 10.1016/j.tcs.2013.09.011

M3 - Article

AN - SCOPUS:84890553119

VL - 516

SP - 101

EP - 120

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -