Stochastic parsing and parallelism

DOI10.1007/3-540-44686-9_39MaRDI QIDQ2763162zbMATH OpenFDO

Authors Francisco-Mario Barcala, Oscar Sacristán, Jorge Graña

Publication date 14 January 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2004/20040401

Mathematics Subject Classification ID

Natural language processing (68T50) Computing methodologies and applications (68U99)

Review text

Parsing CYK-like algorithms are inherently parallel: there are a lot of cells in the chart that can be calculated simultaneously. In this work, we present a study on the appropriate techniques of parallelism to obtain an optimal performance of the \textit{extended CYK algorithm}, a stochastic parsing algorithm that preserves the same level of expressiveness as the one in the original grammar, and improves further tasks of robust parsing. We consider two methods of parallelization: distributed memory and shared memory. The excellent performance obtained with the second one turns this algorithm into an alternative that could compete with other parsing techniques more efficient \textit{a priori}. For the entire collection see [Zbl 0976.68583].

Recommendations

• A parallel parsing algorithm for arbitrary context-free grammars
• Parallel on-line parsing in constant time per word
• scientific article; zbMATH DE number 4119661
• Formulation and analysis of parallel context-free recognition and parsing on a PRAM model
• Parallel recognition and parsing on mesh connected computers with multiple broadcasting

Cited in

(4)

• Parallel parsing of programming languages
• Interleaving natural language parsing and generation through uniform processing
• Massively parallel fault tolerant computations on syntactical patterns
• Parallel \(LL\) parsing

This page was built for publication: Stochastic parsing and parallelism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2763162)