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

PRAMtree adjoining grammarCRCWparallel recognition algorithms

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3926247 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• 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

(3)

• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• 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)