Parallel parsing of tree adjoining grammars on the connection machine
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.
- An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
- scientific article; zbMATH DE number 3926247 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- Routing, merging, and sorting on parallel models of computation
- Speed of Recognition of Context-Free Languages by Array Automata
- Tight bounds for oblivious routing in the hypercube
- Tree adjunct grammars
- Tree-size bounded alternation
- Upper bounds on recognition of a hierarchy of non-context-free languages
- Parallel parsing on the connection machine
- PHRASE parsers from multi-axiom grammars
- TAL recognition in O(M(n^2)) time
- D-LTAG system: Discourse parsing with a lexicalized tree-adjoining grammar
- Enhancing practical TAG parsing efficiency by capturing redundancy
- scientific article; zbMATH DE number 3843161 (Why is no real title available?)
- An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
- scientific article; zbMATH DE number 1974076 (Why is no real title available?)
- Tree-Adjoining Language Parsing in O(n^6 ) Time
- Clique-based lower bounds for parsing tree-adjoining grammars
- An NC algorithm for recognizing tree adjoining languages
This page was built for publication: Parallel parsing of tree adjoining grammars on the connection machine
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685085)
