Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones

DOI10.1007/BF01387511zbMath0842.03040MaRDI QIDQ1908812

Andreas Weiermann

Publication date: 24 July 1996

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

zbMATH Keywords

provably total functionsiterated inductive definitionsordinal notationGrzegorczyk hierarchyhierarchy comparison theoremslow growing hierarchysubrecursive hierarchiessubrecursively inaccessible ordinalssubsystems of KPi

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Second- and higher-order arithmetic and fragments (03F35) Recursive ordinals and ordinal notations (03F15)

Related Items

Term rewriting theory for the primitive recursive functions ⋮ Analytic combinatorics, proof-theoretic ordinals, and phase transitions for independence results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees
• Termination proofs for term rewriting systems by lexicographic path orderings imply multiply recursive derivation lengths
• Term rewriting theory for the primitive recursive functions
• Proof theory. 2nd ed
• A new system of proof-theoretic ordinal functions
• Iterated inductive definitions and subsystems of analysis: recent proof-theoretical studies
• A slow growing analogue to Buchholz' proof
• Ordinal complexity of recursive definitions
• Termination proofs by multiset path orderings imply primitive recursive derivation lengths
• Bounding derivation lengths with functions from the slow growing hierarchy
• Equational derivation vs. computation
• Elementary descent recursion and proof theory
• Proof-theoretic analysis of termination proofs
• Notation systems for infinitary derivations
• Some extensions of built-upness on systems of fundamental sequences
• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Slow growing versus fast growing
• The slow-growing and the Graegorczyk hierarchies
• Π12-logic, Part 1: Dilators
• Built-up systems of fundamental sequences and hierarchies of number-theoretic functions
• P.R.-Regulated Systems of Notation and the Subrecursive Hierarchy Equivalence Property
• Postscript to “built-up systems of fundamental sequences and hierarchies of number-theoretic functions”
• A Uniform Approach to Fundamental Sequences and Hierarchies
• On Wainer's notation for a minimal subrecursive inaccessible ordinal
• Majorisier Ungsrelationen und Fundamentalfolgen eines Ordinalzahlensystems von G. Jäger
• How to characterize provably total functions by local predicativity
• Hierarchies of number-theoretic functions. I
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• Hierarchies of number-theoretic functions II
• A classification of the ordinal recursive functions
• Eine Klassifikation der ε₀‐Rekursiven Funktionen
• Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
• On the interpretation of non-finitist proofs–Part II

This page was built for publication: Investigations on slow versus fast growing: How to majorize slow growing functions nontrivially by fast growing ones