Optimal linear-time parallel parser for tree adjoining languages

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(n⁶) for inputs of length n (as opposed to O(n³) for CFGs). The parallel algorithm achieves optimal speedup: it runs in linear time on a five-dimensional array of n⁵ 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.