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

DOI10.1007/S00224-014-9534-ZMaRDI QIDQ2254497zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

pumping lemmamultiple context-free grammar

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1142312 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• Hierarchy theorems for two-way finite state transducers
• On multiple context-free grammars
• One way finite visit automata
• Pumping lemmas for the control language hierarchy
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• The copying power of well-nested multiple context-free grammars
• The mathematics of language

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
• scientific article; zbMATH DE number 3970128 (Why is no real title available?)

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)