An NC algorithm for recognizing tree adjoining languages

DOI10.1007/BF01408291MaRDI QIDQ685232zbMATH OpenOpenAlexFDO

Authors Michael A. Palis, Sunil Shende

Publication date 30 September 1993

Published in International Journal of Parallel Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01408291

zbMATH Keywords

CRCWparallel recognition algorithmsPRAMtree adjoining grammar

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45) Distributed algorithms (68W15)

Review text

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.

Recommendations

• Tree-Adjoining Language Parsing in O(n^6 ) Time
• Tree adjoining languages and multipushdown languages
• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• Parallel parsing of tree adjoining grammars on the connection machine
• Implementation and Application of Automata

Cites work

• A taxonomy of problems with fast parallel algorithms
• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• scientific article; zbMATH DE number 3926247 (Why is no real title available?)
• On Parsing and Compiling Arithmetic Expressions on Vector Computers
• Optimization of LR(k) parsers
• Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
• Parallel Parsing on a One-Way Array of Finite-State Machines
• Parallel parsing on the connection machine
• Parallel time O(log n) recognition of unambiguous context-free languages
• Simulation of Parallel Random Access Machines by Circuits
• Speed of Recognition of Context-Free Languages by Array Automata
• Tree adjunct grammars
• Tree-size bounded alternation
• Upper Bounds for Speedup in Parallel Parsing
• Upper bounds on recognition of a hierarchy of non-context-free languages

Cited in

(4)

• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• Tree-Adjoining Language Parsing in O(n^6 ) Time
• Implementation and Application of Automata
• Parallel parsing of tree adjoining grammars on the connection machine

This page was built for publication: An NC algorithm for recognizing tree adjoining languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685232)