An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages

DOI10.1137/0219001MaRDI QIDQ3474285zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(7)

• Tabulation of automata for tree-adjoining languages
• An NC algorithm for recognizing tree adjoining languages
• Parallel parsing of tree adjoining grammars on the connection machine
• scientific article; zbMATH DE number 3843161 (Why is no real title available?)
• Dependency structure analysis as combinatorial optimization
• TAL recognition in O(M(n^2)) time
• Enhancing practical TAG parsing efficiency by capturing redundancy

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)