Complexity bounds for some finite forms of Kruskal's theorem
From MaRDI portal
Publication:1892123
DOI10.1006/JSCO.1994.1059zbMATH Open0827.68055OpenAlexW1978060282MaRDI QIDQ1892123FDOQ1892123
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (17)
- The Parametric Complexity of Lossy Counter Machines
- An upper bound on the derivational complexity of Knuth-Bendix orderings.
- Title not available (Why is that?)
- Well-partial-orderings and the big Veblen number
- Title not available (Why is that?)
- Well partial orders
- Linearizing well quasi-orders and bounding the length of bad sequences
- Using unavoidable set of trees to generalize Kruskal's theorem
- Program termination and well partial orderings
- Multiply-recursive upper bounds with Higman's lemma
- Derivation lengths and order types of Knuth--Bendix orders
- The Bachmann-Howard structure in terms of \(\Sigma_1\)-elementarity
- Complexity hierarchies beyond elementary
- Kruskal's tree theorem for acyclic term graphs
- On operations and linear extensions of well partially ordered sets
- Complexity bounds for ordinal-based termination (invited talk)
- Linearizing bad sequences: upper bounds for the product and majoring well quasi-orders
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)
