Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered

DOI10.4230/LIPIcs.FSTTCS.2018.14OpenAlexW2907326504MaRDI QIDQ5090949

Kazuyuki Asada, Naoki Kobayashi

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.fsttcs.2018.14

zbMATH Keywords

well-quasi-orderingpumping lemmaKruskal's tree theoremsimply-typed lambda calculushigher-order grammar

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites Work

• Orderings for term-rewriting systems
• Word operation definable in the typed \(\lambda\)-calculus
• The IO- and OI-hierarchies
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• On word and frontier languages of unsafe higher-order grammars
• Pumping Lemma for Higher-order Languages
• The Complexity of the Diagonal Problem for Recursion Schemes
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Ordering by Divisibility in Abstract Algebras
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lambda-Definable Order-3 Tree Functions are Well-Quasi-Ordered