A shrinking lemma for random forbidding context languages

DOI10.1016/S0304-3975(98)00160-1zbMath0939.68057WikidataQ124833973 ScholiaQ124833973MaRDI QIDQ1566715

Andries P. J. Van der Walt, Sigrid Ewert

Publication date: 4 June 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

formal languagesrandom context languagesregulated rewritingrandom forbidding contextshrinking lemma

Mathematics Subject Classification ID

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

Related Items (16)

On the power of permitting features in cooperating context-free array grammar systems ⋮ Unnamed Item ⋮ A property of random context picture grammars ⋮ On restricted context-free grammars ⋮ Simple restriction in context-free rewriting ⋮ A Pumping Lemma for Permitting Semi-Conditional Languages ⋮ On some derivation mechanisms and the complexity of their Szilard languages ⋮ One-sided forbidding grammars and selective substitution grammars ⋮ Unnamed Item ⋮ Left-forbidding cooperating distributed grammar systems ⋮ A pumping lemma for random permitting context languages ⋮ A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions ⋮ Improved descriptional complexity results on generalized forbidding grammars ⋮ One-sided random context grammars ⋮ On the Complexity of Szilard Languages of Regulated Grammars ⋮ Generalized one-sided forbidding grammars

Cites Work

• Unnamed Item
• Necessary conditions for subclasses of random context languages
• An Algorithm for the General Petri Net Reachability Problem
• A pumping lemma for random permitting context languages

This page was built for publication: A shrinking lemma for random forbidding context languages