Optimal linear-time parallel parser for tree adjoining languages

Michael A. Palis, Sunil Shende, David S.L. Wei

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

An optimal parallel recognition/parsing algorithm is presented for languages generated by tree adjoining grammars (TAGs), a grammatical system for natural language. TAGs are strictly more powerful than context-free grammars (CFGs), e.g., they can generate {a″b″c″|n≥0}, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity O(n6) for inputs of length n (as opposed to O(n3) for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of n5 processors. Moreover, the processors are finite-state; i.e., their function and size depends only on the underlying grammar and not on the length of the input.

Original languageEnglish (US)
Pages (from-to)1-31
Number of pages31
JournalSIAM Journal on Computing
Volume19
Issue number1
DOIs
StatePublished - 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Optimal linear-time parallel parser for tree adjoining languages'. Together they form a unique fingerprint.

Cite this