Sublinear parallel time recognition of tree adjoining languages

Michael A. Palis, Sunil Shende

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


A parallel alorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system which has applications in computational linguistics. This class of languages properly includes all context-free languages; for example, the non-context-free sets {anbn cn} and {ww} are in this class. It is shown that the recognition problem for tree adjoining languages can be solved by a concurrent-read, exclusive-write parallel random-access machine (CREW PRAM) in O(log2(n)) time using polynomially many processors. This extends a previous result for context-free languages.

Original languageEnglish (US)
Pages (from-to)202-205
Number of pages4
JournalProceedings of the International Conference on Parallel Processing
StatePublished - 1989
Externally publishedYes
EventProceedings of the 1989 International Conference on Parallel Processing - University Park, PA, USA
Duration: Aug 8 1989Aug 12 1989

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Sublinear parallel time recognition of tree adjoining languages'. Together they form a unique fingerprint.

Cite this