Parallel parsing of tree adjoining grammars on the connection machine (Q685085)

Tree adjoining grammars (TAGs) were introduced by \textit{A. K. Joshi}, \textit{L. S. Levy}, \textit{M. Takahashi} (1975) mainly as a formalism for natural language specification. The expressive power of TAG formal languages proved to be situated strictly between context-free and context-sensitive languages. A known result is that TAG languages can be parsed in polynomial time (worst-case) \(O(MNn^ 6)\), where \(M\) is the number of TAG elementary trees, \(N\) is the total number of nodes in all elementary trees, and \(n\) is the length of the input sentence. The present paper exposes the authors' effort to improve the sequential but especially the parallel parsing technologies based on TAGs. The main contributions are: (1) A new sequential parsing algorithm, having the runtime complexity \(O(MNnL^ 2)\), where \(L\) is a parameter varying from a constant to \(O(n^ 4)\). The algorithm is better adapted to input variation, and experiments proved an empirical complexity situated between \(O(n)\) and \(O(n^ 2)\); (2) Two parallel parsing algorithms, implemented on a (SIMD parallel architecture) connection machine CM-2; (2a) A first parallel parsing algorithm running nearly linear time in the grammar size \(O(Mn(L+\log N))\), using \(NL\) processors; (2b) The second parallel parsing algorithm runs in time logarithmic in the grammar size, \(O(nL(\log M+\log N))\), using \(MNL\) processors. The modifications to the parsing algorithms describing the processes of the parse tree generation, both in the sequential and parallel settings, are described. The performance results of parallel parsing implementations on a CM-2 machine have been obtained for various (synthetic) TAG grammar sizes.