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

DOI10.1007/s00224-014-9534-zzbMath1319.68128OpenAlexW2077206882WikidataQ125055634 ScholiaQ125055634MaRDI QIDQ2254497

Jens Michaelis, Makoto Kanazawa, Ryo Yoshinaka, Sylvain Salvati, Gregory M. Kobele

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)

Related Items (4)

Comparing consecutive letter counts in multiple context-free languages ⋮ Pumping lemmas for classes of languages generated by folding systems ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• On multiple context-free grammars
• A geometric hierarchy beyond context-free languages
• One way finite visit automata
• Hierarchy theorems for two-way finite state transducers
• The Copying Power of Well-Nested Multiple Context-Free Grammars
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages
• Pumping lemmas for the control language hierarchy

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