Massively Parallel Parsing Algorithms for Natural Language

Michael A. Palis, David S.L. Wei

Research output: Chapter in Book/Report/Conference proceedingChapter


Massively parallel algorithms are described for parsing with Tree Adjoining Grammar (TAG), a formalism for describing natural language. Sequential parsing algorithms for TAGs run in time quadratic in the grammar size, which is impractical for the very large grammars currently being developed for natural language. This paper presents two parallel algorithms, one running in time nearly linear in the grammar size, and the other running in time logarithmic in the grammar size. Both parallel algorithms were implemented on a Connection Machine CM-2 and performance measurements were obtained for varying grammar sizes.

Original languageEnglish (US)
Title of host publicationMachine Intelligence and Pattern Recognition
Number of pages43
StatePublished - Jan 1 1994
Externally publishedYes

Publication series

NameMachine Intelligence and Pattern Recognition
ISSN (Print)0923-0459

All Science Journal Classification (ASJC) codes

  • Computer Vision and Pattern Recognition
  • Artificial Intelligence


Dive into the research topics of 'Massively Parallel Parsing Algorithms for Natural Language'. Together they form a unique fingerprint.

Cite this