A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

DOI10.1007/978-3-642-00982-2_47zbMath1234.68183OpenAlexW2170079385MaRDI QIDQ3618613

Tomáš Masopust

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_47

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (4)

On restricted context-free grammars ⋮ Simple restriction in context-free rewriting ⋮ Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars ⋮ A note on the descriptional complexity of semi-conditional grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A variant of random context grammars: Semi-conditional grammars
• A shrinking lemma for random forbidding context languages
• On the descriptional complexity of some rewriting mechanisms regulated by context conditions
• Descriptional complexity of semi-conditional grammars
• Accepting grammars with regulation
• 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: A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions