A pumping lemma for permitting semi-conditional languages

DOI10.1142/S0129054119400045MaRDI QIDQ5384432zbMATH OpenOpenAlexWikidataFDO

Authors 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 powerpermitting contextsemi-conditional grammars

Mathematics Subject Classification ID

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

Recommendations

• On the power of permitting semi-conditional grammars
• A pumping lemma for random permitting context languages
• A variant of random context grammars: Semi-conditional grammars
• Necessary conditions for subclasses of random context languages
• A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions

Cites work

• A pumping lemma for random permitting context languages
• A shrinking lemma for random forbidding context languages
• A variant of random context grammars: Semi-conditional grammars
• Grammars with partial ordering of the rules
• scientific article; zbMATH DE number 3913706 (Why is no real title available?)
• scientific article; zbMATH DE number 193524 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 5051563 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Necessary conditions for subclasses of random context languages
• On erasing productions in random context grammars
• On restricted context-free grammars
• On the generative capacity of conditional grammars
• On the power of permitting semi-conditional grammars
• Ordering by Divisibility in Abstract Algebras
• Remarks on some simple variants of random context grammars
• Simple restriction in context-free rewriting
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(4)

• On the power of permitting semi-conditional grammars
• A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
• A pumping lemma for random permitting context languages
• Single semi-contextual insertion-deletion systems

This page was built for publication: A pumping lemma for permitting semi-conditional languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384432)