Complexity in left-associative grammar

DOI10.1016/0304-3975(92)90253-CzbMath0787.68064OpenAlexW2019056764WikidataQ127088058 ScholiaQ127088058MaRDI QIDQ1202927

Roland Hausser

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90253-c

zbMATH Keywords

computational complexityrecursive languagesfinite-state automataChomsky hierarchypushdown automatacontinuationscontext-sensitive languagescontext- free languageleft-associative grammarlinearly bounded automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (2)

JSLIM – Computational Morphology in the Framework of the SLIM Theory of Language ⋮ Database semantics for natural language

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• NEWCAT: Parsing natural language using left-associative grammar
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• The Hardest Context-Free Language
• An efficient context-free parsing algorithm
• Studies in abstract families of languages
• On restricting the base component of transformational grammars

This page was built for publication: Complexity in left-associative grammar