Simple restriction in context-free rewriting

DOI10.1016/J.JCSS.2010.04.001zbMath1209.68290OpenAlexW2172260861MaRDI QIDQ1959430

Tomáš Masopust

Publication date: 7 October 2010

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.2010.04.001

zbMATH Keywords

rewriting systemformal languagescontext-free grammarderivation restrictiongenerative power

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

On restricted context-free grammars ⋮ Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1) ⋮ A Pumping Lemma for Permitting Semi-Conditional Languages ⋮ Improved descriptional complexity results on generalized forbidding grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A variant of random context grammars: Semi-conditional grammars
• A shrinking lemma for random forbidding context languages
• Scattered 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
• Accepting grammars with regulation
• Some restrictive devices for context-free grammars
• A pumping lemma for random permitting context languages

This page was built for publication: Simple restriction in context-free rewriting