Parallel parsing algorithm for natural languages using tree adjoining grammar

Tom Nurkkala, Vipin Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Three Adjoining Grammar (TAG) is a powerful grammatical formalism for large-scale natural language processing. However, the computational complexity of parsing algorithms for TAG is high. We introduce a new parallel TAG parsing algorithm for MIMD hypercube multicomputers, using large granularity grammar partitioning, asynchronous communication, and distributed termination detection. We describe our implementation on the nCUBE/2 parallel computer, and provide experimental results on both random and English grammars. Our algorithm delivers the best performance of any TAG parsing algorithm to date, yielding an almost two order-of-magnitude speedup and good efficiency on up to 256 processors.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
PublisherPubl by IEEE
Pages820-828
Number of pages9
ISBN (Print)0818656026
StatePublished - Jan 1 1994
EventProceedings of the 8th International Parallel Processing Symposium - Cancun, Mex
Duration: Apr 26 1994Apr 29 1994

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Other

OtherProceedings of the 8th International Parallel Processing Symposium
CityCancun, Mex
Period4/26/944/29/94

Fingerprint Dive into the research topics of 'Parallel parsing algorithm for natural languages using tree adjoining grammar'. Together they form a unique fingerprint.

Cite this