Research output: Contribution to journal › Article › peer-review
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.
Original language | English |
---|---|
Pages (from-to) | 101-120 |
Number of pages | 20 |
Journal | Theoretical Computer Science |
Volume | 516 |
DOIs | |
State | Published - 9 Jan 2014 |
ID: 41140193