On restricted context-free grammars

DOI10.1016/J.JCSS.2011.05.008zbMath1247.68117OpenAlexW1999932874MaRDI QIDQ414885

Tomáš Masopust, Juergen Dassow

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.008

zbMATH Keywords

normal formscontext-free grammarsderivation restrictiongenerative power

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (3)

Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ A Pumping Lemma for Permitting Semi-Conditional Languages ⋮ On the computational completeness of generalized forbidding matrix grammars

Cites Work

• Unnamed Item
• Unnamed Item
• A variant of random context grammars: Semi-conditional grammars
• A shrinking lemma for random forbidding context languages
• Simple restriction in context-free rewriting
• On Erasing Productions in Random Context Grammars
• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions
• On context-free rewriting with a simple restriction and its computational completeness
• One-sided and two-sided context in formal grammars
• Some restrictive devices for context-free grammars
• Grammars with Context Conditions and Their Applications
• A pumping lemma for random permitting context languages

This page was built for publication: On restricted context-free grammars