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

DOI10.4230/LIPICS.FSTTCS.2018.14MaRDI QIDQ5090949zbMATH OpenOpenAlexFDO

Authors 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

pumping lemmawell-quasi-orderingKruskal'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)

Recommendations

• Pumping Lemma for Higher-order Languages
• On the generalization of Higman and Kruskal's theorems to regular languages and rational trees
• A theorem on labelled trees and the limits of its provability
• Pumping by typing
• Generalizations of the Kruskal-Friedman theorems

Cites work

• scientific article; zbMATH DE number 3478415 (Why is no real title available?)
• scientific article; zbMATH DE number 475247 (Why is no real title available?)
• scientific article; zbMATH DE number 2079020 (Why is no real title available?)
• On derivation trees of indexed grammars - an extension of the uvwxy- theorem
• On word and frontier languages of unsafe higher-order grammars
• Ordering by Divisibility in Abstract Algebras
• Orderings for term-rewriting systems
• Pumping Lemma for Higher-order Languages
• The Complexity of the Diagonal Problem for Recursion Schemes
• The IO- and OI-hierarchies
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Word operation definable in the typed \(\lambda\)-calculus

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

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