An NC algorithm for recognizing tree adjoining languages |
| |
Authors: | Michael A Palis Sunil M Shende |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, New Jersey Institute of Technology, 07102 Newark, New Jersey;(2) Department of Computer Science and Engineering, University of Nebraska at Lincoln, 68588 Lincoln, Nebraska |
| |
Abstract: | A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system which has applications in natural language processing. This class of languages is known to properly include all context-free languages; for example, the noncontext-free sets {a
n
b
n
c
n
} and {ww} are in this class. It is shown that the recognition problem for tree adjoining languages can be solved by a concurrent read, concurrent write parallel random-access machine (CRCW PRAM) inO(logn) time using polynomially many processors. Thus, the class of tree adjoining languages is inAC
1 and hence inNC. This extends a previous result for context-free languages.This research was supported in part by NSF Grants IRI 92-96249, MCS 82-19116-CER, MCS 82-07294, DCR 84-10413, MCS 83-05221, ARO Grant DAA29-84-9-0027, DARPA Grant N00014-85-K-0018, and by the New Jersey Institute of Technology under Grant Nos. 421690 and 211665. |
| |
Keywords: | Language recognition tree adjoining grammar PRAM paralle complexity classes |
本文献已被 SpringerLink 等数据库收录! |
|