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

DOI10.4230/LIPICS.FSTTCS.2018.14OpenAlexW2907326504MaRDI QIDQ5090949FDOQ5090949

Authors: Kazuyuki Asada, Naoki Kobayashi 

Publication date: 21 July 2022

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

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

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)

Cites Work

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

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)