An NC algorithm for recognizing tree adjoining languages (Q685232)

The Tree Adjoining Grammar (TAG) is a tree rewriting system that uses the operation called adjunction to compose larger (derived) trees from a finite set of basic (elementary) trees. The authors (and D. S. L. Wei) have shown (1990) that TA languages (TALs) can be recognized by a parallel algorithm running in \(0(n)\) time using polynomially many processors. The present paper proves that the TAL recognition problem can be solved by a concurrent-read concurrent-write parallel random-access machine (CRCW PRAM) in \(0(\log n)\) time and using \(0(n^{12})\) processors. This result places TALs in the class \({\mathcal A}{\mathcal C}^ 1\) of languages accepted by an alternating Turing machine in space \(0(\log n)\) and alternation depth \(0(\log n)\), and effectively extends the \textit{W. L. Ruzzo}'s [Automata, languages and programming, 6th Collow., Graz 1979, Lect. Notes Comput. Sci. 71, 489-497 (1979; Zbl 0409.68024)] results according to which context-free languages belong to \({\mathcal A}{\mathcal C}^ 1\) too. Investigating the place of TALs within the \textit{D. J. Weir}'s [Theoret. Comput. Sci. 104, No. 2, 235-261 (1992; Zbl 0754.68070)] Control Language Hierarchy is proposed.