Pumping Lemma for Higher-order Languages

DOI10.4230/LIPICS.ICALP.2017.97zbMATH Open1442.68078arXiv1705.10699OpenAlexW2963912948MaRDI QIDQ5111429FDOQ5111429

Naoki Kobayashi, Kazuyuki Asada

Publication date: 27 May 2020

Abstract: We study a pumping lemma for the word/tree languages generated by higher-order grammars. Pumping lemmas are known up to order-2 word languages (i.e., for regular/context-free/indexed languages), and have been used to show that a given language does not belong to the classes of regular/context-free/indexed languages. We prove a pumping lemma for word/tree languages of arbitrary orders, modulo a conjecture that a higher-order version of Kruskal's tree theorem holds. We also show that the conjecture indeed holds for the order-2 case, which yields a pumping lemma for order-2 tree languages and order-3 word languages.

Full work available at URL: https://arxiv.org/abs/1705.10699

Recommendations

• A pumping lemma for deterministic context-free languages
• Pumping lemmas for special linear languages
• A pumping lemma for flip-pushdown languages
• Pumping lemmas for the control language hierarchy
• Formalization of the pumping lemma for context-free languages
• Pumping lemmas for linear and nonlinear context-free languages
• A pumping lemma for \textbf{DLI}-languages
• scientific article; zbMATH DE number 3902063
• Pumping lemmas for classes of languages generated by folding systems
• The Pumping Lemma for Well-Nested Multiple Context-Free Languages

zbMATH Keywords

pumping lemmaKruskal's tree theoremhigher-order grammars

Mathematics Subject Classification ID

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

Cited In (7)

• Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered
• Pumping for ordinal-automatic structures1
• The Complexity of the Diagonal Problem for Recursion Schemes
• Pumping lemmas for special linear languages
• A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
• Title not available (Why is that?)
• Pumping lemmas for classes of languages generated by folding systems

This page was built for publication: Pumping Lemma for Higher-order Languages

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