Derivational complexity of context-free grammars

DOI10.1016/S0019-9958(82)91111-1MaRDI QIDQ3321486zbMATHFDO

Authors Seppo Sippu

Publication date 1982

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

context-free grammarsderivational time and space complexityminimal grammar dependent boundsminimal linear boundsnumber of derivation steps

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the synchronized derivation depth of context-free grammars
• On the degrees of non-regularity and non-context-freeness
• Descriptional complexity of context-free grammar forms
• scientific article; zbMATH DE number 3850491
• scientific article; zbMATH DE number 1738663

Cited in

(12)

• Context free derivations on word monoids
• scientific article; zbMATH DE number 3919851 (Why is no real title available?)
• Constraints on derivations
• A COMPLEX MEASURE FOR LINEAR GRAMMARS
• scientific article; zbMATH DE number 58320 (Why is no real title available?)
• More on the power of chain rules in context-free grammars
• On the synchronized derivation depth of context-free grammars
• Computing a context-free grammar-generating series
• Derived linear systems of context-free grammars
• A scheme for LR(k) parsing with error recovery part II: error recovery
• Die Grösse des Minimalen Analysators Einer Kontextfreien Grammatik
• On some derivation mechanisms and the complexity of their Szilard languages

This page was built for publication: Derivational complexity of context-free grammars

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