Control structures in programs and computational complexity

DOI10.1016/J.APAL.2004.10.011MaRDI QIDQ1772780zbMATH OpenOpenAlexFDO

Authors 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

Implicit computational complexityLambda calculusPolynomial timeGrzegorczyk hierarchyHigher-type recursionImperative programming languages

Mathematics Subject Classification ID

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

Recommendations

• A unifying theory of control dependence and its application to arbitrary program structures
• The Hierarchy of Program Control Structures
• Programmed constructions for control synthesis problems
• scientific article; zbMATH DE number 822348
• Complexity analysis in presence of control operators and higher-order functions
• scientific article; zbMATH DE number 4170755
• scientific article; zbMATH DE number 3952529
• Publication:4945219

Cites work

• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Higher type recursion, ramification and polynomial time
• Iteration of Primitive Recursion
• On the computational complexity of imperative programming languages
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• The Garland measure and computational complexity of stack programs
• The \(\mu\)-measure as a tool for classifying computational complexity

Cited in

(9)

• Efficient computation of arbitrary control dependencies
• A Refinement of the μ-measure for Stack Programs
• Implicit characterizations of FPTIME and NC revisited
• On the computational complexity of imperative programming languages
• The Garland measure and computational complexity of stack programs
• Supporting control definition in programming languages
• Widening with Thresholds for Programs with Complex Control Graphs
• scientific article; zbMATH DE number 822348 (Why is no real title available?)
• scientific article; zbMATH DE number 3856409 (Why is no real title available?)

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

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