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

Grzegorczyk hierarchyHigher-type recursionImperative programming languagesImplicit computational complexityLambda calculusPolynomial time

Mathematics Subject Classification ID

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

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
• scientific article; zbMATH DE number 1424029

Cites work

• A new recursion-theoretic characterization of the polytime functions
• Higher type recursion, ramification and polynomial time
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• 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 \(\mu\)-measure as a tool for classifying computational complexity
• The Garland measure and computational complexity of stack programs

Cited in

(9)

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

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)