A parallel algorithm for counting parse trees

A parallel algorithm for computing the number of parse trees of a given string according to a fixed context-free grammar is defined. More generally, the algorithm applies to computing the weight of a string in a weighted grammar over any semiring. The algorithm is first implemented on an arithmetic circuit of depth at most 6 ( log 2 ⁡ n ) 2 + O ( log ⁡ n ) and with O ( n 6 ) elements, where the constant factors in the big-O notation depend on the grammar. Then, the circuit is improved using fast matrix multiplication to use only O ( n 5. 38 ) elements, while preserving depth O ( ( log ⁡ n ) 2 ).

Authors

• Margarita Mikhelson
• Alexander Okhotin

Keywords

• Context-free grammars
• Weighted grammars
• Parsing
• Parallel algorithms
• Matrix multiplication