A pumping lemma for random permitting context languages

DOI10.1016/S0304-3975(01)00171-2zbMath0988.68099OpenAlexW1991556569WikidataQ125020030 ScholiaQ125020030MaRDI QIDQ5958343

Andries P. J. Van der Walt, Sigrid Ewert

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00171-2

zbMATH Keywords

formal languagespumping lemmarandom context languagesrandom permitting contextregulated rewriting

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

On the power of permitting features in cooperating context-free array grammar systems ⋮ 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 ⋮ Left-forbidding cooperating distributed grammar systems ⋮ A Note on the Generative Power of Some Simple Variants of Context-Free Grammars Regulated by Context Conditions ⋮ A shrinking lemma for random forbidding context languages ⋮ One-sided random context grammars ⋮ On the Complexity of Szilard Languages of Regulated Grammars

Cites Work

• Unnamed Item
• Unnamed Item
• More on ETOL systems versus random context grammars
• A shrinking lemma for random forbidding context languages
• An Algorithm for the General Petri Net Reachability Problem

This page was built for publication: A pumping lemma for random permitting context languages