Descriptional complexity of context-free grammar forms

DOI10.1016/0304-3975(93)90021-KMaRDI QIDQ1210294zbMATH OpenOpenAlexWikidataFDO

Authors Erzsébet Csuhaj-Varjú, Alica Kelemenová

Publication date 24 May 1993

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

Full work available at URL https://doi.org/10.1016/0304-3975(93)90021-k

zbMATH Keywords

descriptional complexitygrammatical complexity measuresinfinite class of languagesinfinite grammar form

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 4039331
• scientific article; zbMATH DE number 3850491
• Complexity of normal form grammars
• Descriptional complexity of semi-conditional grammars
• Descriptional complexity of multi-parallel grammars

Cites work

• Complexity of normal form grammars
• Grammar and L forms: an introduction
• scientific article; zbMATH DE number 4039331 (Why is no real title available?)
• scientific article; zbMATH DE number 3742654 (Why is no real title available?)
• scientific article; zbMATH DE number 3254902 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• On bounded interpretations of grammar forms
• Some classifications of context-free languages

Cited in

(20)

• Estimating the execution complexity of logical specifications based on context-free grammars
• Grammar efficiency and complexity
• scientific article; zbMATH DE number 428239 (Why is no real title available?)
• scientific article; zbMATH DE number 3850491 (Why is no real title available?)
• Derivational complexity of context-free grammars
• On the descriptional complexity of CD grammar systems of finite index
• A REGULARITY CONDITION FOR CONTEXT-FREE GRAMMARS
• scientific article; zbMATH DE number 5506908 (Why is no real title available?)
• scientific article; zbMATH DE number 3919851 (Why is no real title available?)
• scientific article; zbMATH DE number 3924157 (Why is no real title available?)
• scientific article; zbMATH DE number 4009837 (Why is no real title available?)
• scientific article; zbMATH DE number 4028929 (Why is no real title available?)
• scientific article; zbMATH DE number 4039331 (Why is no real title available?)
• scientific article; zbMATH DE number 4108173 (Why is no real title available?)
• scientific article; zbMATH DE number 1952666 (Why is no real title available?)
• scientific article; zbMATH DE number 1998334 (Why is no real title available?)
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Improved descriptional complexity results on generalized forbidding grammars
• Improved descriptional complexity results on generalized forbidding grammars
• On the grammatical complexity of finite languages

This page was built for publication: Descriptional complexity of context-free grammar forms

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