Pumping Lemma for Higher-order Languages
From MaRDI portal
Publication:5111429
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.
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
Cited in
(10)- 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
- Pumping by typing
- A PUMPING CONDITION FOR ULTRALINEAR LANGUAGES
- On word and frontier languages of unsafe higher-order grammars
- Unsafe order-2 tree languages are context-sensitive
- scientific article; zbMATH DE number 7526052 (Why is no real title available?)
- 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)
