Complexity bounds for some finite forms of Kruskal's theorem
From MaRDI portal
Publication:1892123
DOI10.1006/jsco.1994.1059zbMath0827.68055OpenAlexW1978060282MaRDI QIDQ1892123
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
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