The failure of the strong pumping lemma for multiple context-free languages

DOI10.1007/S00224-014-9534-ZzbMATH Open1319.68128OpenAlexW2077206882WikidataQ125055634 ScholiaQ125055634MaRDI QIDQ2254497FDOQ2254497

Authors: Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, S. Salvati, Ryo Yoshinaka 

Publication date: 5 February 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9534-z

Recommendations

• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• A pumping lemma for deterministic context-free languages
• scientific article; zbMATH DE number 1222097
• Some applications of the formalization of the pumping lemma for context-free languages
• A pumping result for 2-context-free languages
• Formalization of the pumping lemma for context-free languages
• Pumping lemmas for linear and nonlinear context-free languages
• Comparisons between some pumping conditions for context-free languages
• A pumping lemma for random permitting context languages
• scientific article; zbMATH DE number 3970128

zbMATH Keywords

pumping lemmamultiple context-free grammar

Mathematics Subject Classification ID

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

Cites Work

• A geometric hierarchy beyond context-free languages
• On multiple context-free grammars
• Title not available (Why is that?)
• The mathematics of language
• One way finite visit automata
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Pumping lemmas for the control language hierarchy
• Hierarchy theorems for two-way finite state transducers
• The copying power of well-nested multiple context-free grammars

Cited In (6)

• Comparing consecutive letter counts in multiple context-free languages
• MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies
• Ogden's lemma, multiple context-free grammars, and the control language hierarchy
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Pumping lemmas for classes of languages generated by folding systems
• Title not available (Why is that?)

This page was built for publication: The failure of the strong pumping lemma for multiple context-free languages

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