Complexity in left-associative grammar

DOI10.1016/0304-3975(92)90253-CMaRDI QIDQ1202927zbMATH OpenOpenAlexWikidataFDO

Authors 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 complexityChomsky hierarchyfinite-state automatapushdown automatacontinuationscontext-sensitive languagesrecursive languagescontext- free languageleft-associative grammarlinearly bounded automata

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 43628
• NEWCAT: Parsing natural language using left-associative grammar
• scientific article; zbMATH DE number 777296
• On multiple context-free grammars
• On parsing coupled-context-free languages

Cites work

• scientific article; zbMATH DE number 3868642 (Why is no real title available?)
• scientific article; zbMATH DE number 43628 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• An efficient context-free parsing algorithm
• NEWCAT: Parsing natural language using left-associative grammar
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• On restricting the base component of transformational grammars
• Studies in abstract families of languages
• The Hardest Context-Free Language

Cited in

(4)

• A COMPLEX MEASURE FOR LINEAR GRAMMARS
• JSLIM -- computational morphology in the framework of the SLIM theory of language
• Database semantics for natural language
• NEWCAT: Parsing natural language using left-associative grammar

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

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