A Pumping Lemma for Permitting Semi-Conditional Languages

DOI10.1142/S0129054119400045zbMath1415.68118OpenAlexW2919882210WikidataQ125053949 ScholiaQ125053949MaRDI QIDQ5384432

Zsolt Gazdag, Krisztián Tichler, Erzsébet Csuhaj-Varjú

Publication date: 24 June 2019

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054119400045

zbMATH Keywords

generative powersemi-conditional grammarspermitting context

Mathematics Subject Classification ID

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

Related Items (1)

Single semi-contextual insertion-deletion systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On restricted context-free grammars
• A variant of random context grammars: Semi-conditional grammars
• A shrinking lemma for random forbidding context languages
• Necessary conditions for subclasses of random context languages
• Simple restriction in context-free rewriting
• On the power of permitting semi-conditional grammars
• On Erasing Productions in Random Context Grammars
• On the generative capacity of conditional grammars
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Grammars with partial ordering of the rules
• Ordering by Divisibility in Abstract Algebras
• A pumping lemma for random permitting context languages

This page was built for publication: A Pumping Lemma for Permitting Semi-Conditional Languages