Control structures in programs and computational complexity

DOI10.1016/j.apal.2004.10.011zbMath1064.68029OpenAlexW1970467575MaRDI QIDQ1772780

Karl-Heinz Niggl

Publication date: 21 April 2005

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2004.10.011

zbMATH Keywords

Lambda calculusImplicit computational complexityPolynomial timeGrzegorczyk hierarchyHigher-type recursionImperative programming languages

Mathematics Subject Classification ID

Theory of programming languages (68N15) Functional programming and lambda calculus (68N18) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (2)

A Refinement of the μ-measure for Stack Programs ⋮ Implicit characterizations of FPTIME and NC revisited

Cites Work

• Unnamed Item
• A new recursion-theoretic characterization of the polytime functions
• Higher type recursion, ramification and polynomial time
• The \(\mu\)-measure as a tool for classifying computational complexity
• On the computational complexity of imperative programming languages
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• The Garland Measure and Computational Complexity of Stack Programs
• Iteration of Primitive Recursion
• Rekursionszahlen und die Grzegorczyk-Hierarchie

This page was built for publication: Control structures in programs and computational complexity