Descriptional complexity of semi-conditional grammars

DOI10.1016/J.IPL.2007.05.002MaRDI QIDQ2379990zbMATH OpenOpenAlexFDO

Authors Tomáš Masopust, Alexander Meduna

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.05.002

zbMATH Keywords

descriptional complexityformal languagessemi-conditional grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• New nonterminal complexity results for semi-conditional grammars
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• scientific article; zbMATH DE number 1870506
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• Descriptional complexity of multi-parallel grammars

Cites work

• A variant of random context grammars: Semi-conditional grammars
• Grammars with Context Conditions and Their Applications
• scientific article; zbMATH DE number 3913706 (Why is no real title available?)
• scientific article; zbMATH DE number 4064526 (Why is no real title available?)
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions

Cited in

(20)

• Descriptional complexity of context-free grammar forms
• Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case
• New nonterminal complexity results for semi-conditional grammars
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Generalized forbidding matrix grammars and their membrane computing perspective
• Descriptional complexity of matrix simple semi-conditional grammars
• scientific article; zbMATH DE number 5506908 (Why is no real title available?)
• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• scientific article; zbMATH DE number 3990895 (Why is no real title available?)
• scientific article; zbMATH DE number 4068327 (Why is no real title available?)
• scientific article; zbMATH DE number 1870506 (Why is no real title available?)
• Descriptional Complexity Of Generalized Forbidding Grammars
• CONDITIONAL GRAMMARS WITH RESTRICTIONS BY SYNTACTIC PARAMETERS
• Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars
• Simple-semi-conditional versions of matrix grammars with a reduced regulating mechanism
• Improved descriptional complexity results on generalized forbidding grammars
• Non-simple rule counting in semi-conditional grammars
• Counting simple rules in semi-conditional grammars is not simple
• Descriptional complexity of multi-parallel grammars
• A note on the descriptional complexity of semi-conditional grammars

This page was built for publication: Descriptional complexity of semi-conditional grammars

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