Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited

DOI10.1137/S009753979528175XzbMath0939.03042OpenAlexW1981528174MaRDI QIDQ4268889

Karl-Heinz Niggl, Stephen J. Bellantoni

Publication date: 28 October 1999

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753979528175x

zbMATH Keywords

computational complexitylinear spacepolynomial timepredicativityGrzegorczyk hierarchysubrecursionramified recursionHeinermann classes

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)

Related Items

The Garland Measure and Computational Complexity of Stack Programs ⋮ Control structures in programs and computational complexity ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ Separating NC along the \(\delta\) axis ⋮ On the computational complexity of imperative programming languages ⋮ Higher type recursion, ramification and polynomial time ⋮ Implicit characterizations of FPTIME and NC revisited