One-sided random context grammars

DOI10.1007/s00236-011-0134-yzbMath1234.68184OpenAlexW1983841063MaRDI QIDQ766166

Alexander Meduna, Petr Zemek

Publication date: 23 March 2012

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00236-011-0134-y

zbMATH Keywords

context-sensitive languagescontext-free-based regulated grammarerasing rulesforbidding symbolsone-sided random context grammarpermitting symbolsrandom context rules

Mathematics Subject Classification ID

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

Related Items

Regulated variants of limited context restarting automata ⋮ One-Sided Random Context Grammars with Leftmost Derivations ⋮ One-sided random context grammars with a limited number of right random context rules ⋮ One-Sided Random Context Grammars: A Survey ⋮ Nonterminal complexity of one-sided random context grammars ⋮ One-sided forbidding grammars and selective substitution grammars ⋮ Generalized one-sided forbidding grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Left-forbidding cooperating distributed grammar systems
• A variant of random context grammars: Semi-conditional grammars
• A shrinking lemma for random forbidding context languages
• Scattered context grammars
• A note on leftmost restricted random context grammars
• Random Context in Regulated Rewriting Versus Cooperating Distributed Grammar Systems
• On Erasing Productions in Random Context Grammars
• One-sided and two-sided context in formal grammars
• Grammars with Context Conditions and Their Applications
• A pumping lemma for random permitting context languages