Complexity bounds for some finite forms of Kruskal's theorem

DOI10.1006/jsco.1994.1059zbMath0827.68055OpenAlexW1978060282MaRDI QIDQ1892123

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)

Related Items

The Bachmann-Howard structure in terms of \(\Sigma_1\)-elementarity, An upper bound on the derivational complexity of Knuth-Bendix orderings., Unnamed Item, Unnamed Item, Multiply-Recursive Upper Bounds with Higman’s Lemma, Well-partial-orderings and the big Veblen number, On operations and linear extensions of well partially ordered sets, Derivation lengths and order types of Knuth--Bendix orders, Linearizing well quasi-orders and bounding the length of bad sequences, The Parametric Complexity of Lossy Counter Machines, Complexity Hierarchies beyond Elementary