DOI

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(log2⁡n)2+O(log⁡n) and with O(n6) 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(n5.38) elements, while preserving depth O((log⁡n)2).
Язык оригиналаанглийский
Номер статьи105237
Число страниц19
ЖурналInformation and Computation
Том303
DOI
СостояниеОпубликовано - 1 мар 2025

ID: 131232926