Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited

DOI10.1137/S009753979528175XMaRDI QIDQ4268889zbMATH OpenOpenAlexFDO

Authors 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 complexityGrzegorczyk hierarchyHeinermann classeslinear spacepolynomial timepredicativityramified recursionsubrecursion

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 3557782
• scientific article; zbMATH DE number 19768
• Grzegorcyk's hierarchy and IepΣ₁

Cited in

(18)

• Implicit characterizations of FPTIME and NC revisited
• An inherently iterative algorithm for the Grzegorczyk hierarchy
• Higher type recursion, ramification and polynomial time
• The \(\mu\)-measure as a tool for classifying computational complexity
• Control structures in programs and computational complexity
• Separating NC along the \(\delta\) axis
• On the computational complexity of imperative programming languages
• Function operators spanning the arithmetical and the polynomial hierarchy
• Pure Iteration and Periodicity
• scientific article; zbMATH DE number 3557764 (Why is no real title available?)
• scientific article; zbMATH DE number 3557782 (Why is no real title available?)
• Grzegorcyk's hierarchy and IepΣ₁
• Characterization of the Relations in Grzegorczyk's Hierarchy Revisited
• Some Hierarchies of Primitive Recursive Functions on Term Algebras
• scientific article; zbMATH DE number 1114016 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• The Garland measure and computational complexity of stack programs
• scientific article; zbMATH DE number 1390026 (Why is no real title available?)

This page was built for publication: Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4268889)