Ranking primitive recursions: The low Grzegorczyk classes revisited
Traditional results in subrecursion theory are integrated with the recent work in "predicative recursion" by defining a simple ranking rho of all primitive recursive functions. The hierarchy defined by this ranking coincides with the Grzegorczyk hierarchy at and above the linear-space level. Thus, the result is like an extension of the Schwichtenberg-Muller theorems. When primitive recursion is replaced by recursion on notation, the same series of classes is obtained except with the polynomial time computable functions at the first level.
subrecursion predicativity polynomial time computational complexity ramified recursion heinermann classes linear space