Complexity bounds for some finite forms of Kruskal's theorem

DOI10.1006/JSCO.1994.1059MaRDI QIDQ1892123zbMATH OpenOpenAlexFDO

Authors Andreas Weiermann

Publication date 8 June 1995

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jsco.1994.1059

zbMATH Keywords

Kruskal's theoremcomputational complexity of algorithmswell-partial orders

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Complexity bounds for ordinal-based termination (invited talk)
• Well-partial orderings and their maximal order types
• Using unavoidable set of trees to generalize Kruskal's theorem
• Generalizations of the Kruskal-Friedman theorems
• Higher-Order Termination: From Kruskal to Computability

Cited in

(17)

• An upper bound on the derivational complexity of Knuth-Bendix orderings.
• Multiply-recursive upper bounds with Higman's lemma
• Derivation lengths and order types of Knuth--Bendix orders
• Using unavoidable set of trees to generalize Kruskal's theorem
• The Parametric Complexity of Lossy Counter Machines
• Well partial orders
• Statures and sobrification ranks of Noetherian spaces
• Linearizing well quasi-orders and bounding the length of bad sequences
• The Bachmann-Howard structure in terms of \(\Sigma_1\)-elementarity
• Complexity bounds for ordinal-based termination (invited talk)
• scientific article; zbMATH DE number 7379291 (Why is no real title available?)
• Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
• Program termination and well partial orderings
• Kruskal's tree theorem for acyclic term graphs
• On operations and linear extensions of well partially ordered sets
• Complexity hierarchies beyond elementary
• Well-partial-orderings and the big Veblen number

This page was built for publication: Complexity bounds for some finite forms of Kruskal's theorem

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