An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages

DOI10.1137/0219001zbMATH Open0696.68095OpenAlexW2053309264MaRDI QIDQ3474285FDOQ3474285

Authors: Michael A. Palis, David S. L. Wei, Sunil Shende 

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219001

Recommendations

• Parallel parsing of tree adjoining grammars on the connection machine
• On the complexity of parallel parsing of general context-free languages
• Tree-Adjoining Language Parsing in $O(n^6 )$ Time
• Optimal parallel parsing of bracket languages
• An NC algorithm for recognizing tree adjoining languages

zbMATH Keywords

parsingtree adjoining grammarsmesh-connected processor arrays

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Cellular automata (computational aspects) (68Q80) Natural language processing (68T50)

Cited In (7)

• An NC algorithm for recognizing tree adjoining languages
• Parallel parsing of tree adjoining grammars on the connection machine
• Title not available (Why is that?)
• Dependency structure analysis as combinatorial optimization
• TAL recognition in \(O(M(n^2))\) time
• Enhancing practical TAG parsing efficiency by capturing redundancy
• Tabulation of automata for tree-adjoining languages

This page was built for publication: An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages

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