An NC algorithm for recognizing tree adjoining languages

A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system that has applications in natural language processing. This class of languages is known to properly include all context-free languages. The analysis shows that the re...

Full description

Saved in:
Bibliographic Details
Published in:International journal of parallel programming 1992-04, Vol.21 (2), p.151-167
Main Authors: Palis, Michael A, Shende, Sunil M
Format: Article
Language:English
Subjects:
990200 - Mathematics & Computers
ALGORITHMS
Computer languages
DATA-FLOW PROCESSING
GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE
Information processing
MATHEMATICAL LOGIC
Numerical controls
OPTIMIZATION
PARALLEL PROCESSING
PROGRAMMING
Studies
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A parallel algorithm is presented for recognizing the class of languages generated by tree adjoining grammars, a tree rewriting system that has applications in natural language processing. This class of languages is known to properly include all context-free languages. The analysis shows that the recognition problem for tree adjoining languages (TALs) can be solved by a concurrent read, concurrent write parallel random access machine (CRCW PRAM) in O(log n) time using polynomially many processors. The processor-time product of the algorithm is, however, not optimal. Indeed, it is an interesting open problem whether there is an optimal parallel recognition algorithm for TALs, or even for context-free languages, that runs in sublinear time. Further analysis has shown that the 2nd level of a hierarchy of languages called the control language hierarchy (CLH) is equivalent to the class of TALs.
ISSN:0885-7458
1573-7640
DOI:10.1007/BF01408291