An NC algorithm for recognizing tree adjoining languages

DOI10.1007/BF01408291zbMath0777.68059MaRDI QIDQ685232

Michael A. Palis, Sunil M. Shende

Publication date: 30 September 1993

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

zbMATH Keywords

tree adjoining grammar; PRAM; CRCW; parallel recognition algorithms

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W15: Distributed algorithms

Cites Work

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