TAL recognition in \(O(M(n^2))\) time

DOI10.1006/jcss.1997.1537zbMath0914.68122OpenAlexW2466282785MaRDI QIDQ1267714

Shibu Yooseph, Sanguthevar Rajasekaran

Publication date: 21 June 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1537

zbMATH Keywords

parsing

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42)

Related Items (3)

Linearity and nondeletion on monadic context-free tree grammars ⋮ Parsing by matrix multiplication generalized to Boolean grammars ⋮ Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

Cites Work

• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Mathematical methods in linguistics
• General context-free recognition in less than cubic time
• Tree adjunct grammars
• An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages
• Tree-Adjoining Language Parsing in $O(n^6 )$ Time

This page was built for publication: TAL recognition in \(O(M(n^2))\) time