Derivational complexity of context-free grammars

DOI10.1016/S0019-9958(82)91111-1zbMATH Open0536.68064MaRDI QIDQ3321486FDOQ3321486

Authors: Seppo Sippu 

Publication date: 1982

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

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

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)

Cited In (12)

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

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)