An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
Michael A. Palis, Sunil M. Shende, David S. L. Wei · SIAM Journal on Computing · 1990
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 \geqq 0\}$, which is not context-free. However, serial parsing of TAGs is also slower, having time complexity $O(n^{6})$ for inputs of length n (as opposed to $O(n^{3})$ for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of $n^5$ 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.