Bounding derivation lengths with functions from the slow growing hierarchy

DOI10.1007/s001530050107zbMath0919.03036OpenAlexW2092340582MaRDI QIDQ1267850

Andreas Weiermann

Publication date: 19 August 1999

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001530050107

zbMATH Keywords

growth rateterm rewrite systemsderivation lengthstermination orderingcomplexity characterizationshierarchy comparison theoremslow growing hierarchysubrecursive hierarchies

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Recursive functions and relations, subrecursive hierarchies (03D20) Recursive ordinals and ordinal notations (03F15) Complexity of proofs (03F20)

Related Items

How is it that infinitary methods can be applied to finitary mathematics? Gödel's T: a case study, Problems in rewriting III, Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones, The hierarchy of terminating recursive programs over N, Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths, Term rewriting theory for the primitive recursive functions, Some results on cut-elimination, provable well-orderings, induction and reflection