An NC algorithm for recognizing tree adjoining languages

DOI10.1007/BF01408291zbMath0777.68059OpenAlexW1990102452MaRDI QIDQ685232

Michael A. Palis, Sunil M. 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

tree adjoining grammarPRAMCRCWparallel recognition algorithms

Mathematics Subject Classification ID

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

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

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