On the computational complexity of imperative programming languages

DOI10.1016/J.TCS.2003.10.016MaRDI QIDQ1827396zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 6 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2003.10.016

zbMATH Keywords

Implicit computational complexityGrzegorczyk hierarchyImperative programming languagesPolynomial-time computabilitySubrecursion theory

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Recommendations

• A Refinement of the μ-measure for Stack Programs
• The Garland measure and computational complexity of stack programs
• Control structures in programs and computational complexity
• Simple programming languages and restricted classes of Turing machines
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs

Cites work

• scientific article; zbMATH DE number 445159 (Why is no real title available?)
• scientific article; zbMATH DE number 3857078 (Why is no real title available?)
• scientific article; zbMATH DE number 176211 (Why is no real title available?)
• scientific article; zbMATH DE number 1018349 (Why is no real title available?)
• scientific article; zbMATH DE number 1114331 (Why is no real title available?)
• scientific article; zbMATH DE number 2079048 (Why is no real title available?)
• scientific article; zbMATH DE number 1499100 (Why is no real title available?)
• scientific article; zbMATH DE number 806743 (Why is no real title available?)
• scientific article; zbMATH DE number 806752 (Why is no real title available?)
• scientific article; zbMATH DE number 1390027 (Why is no real title available?)
• scientific article; zbMATH DE number 3083488 (Why is no real title available?)
• A new recursion-theoretic characterization of the polytime functions
• Augmented loop languages and classes of computable functions
• Classes of Predictably Computable Functions
• Function-algebraic characterizations of log and polylog parallel time
• Hierarchies of Primitive Recursive Functions
• Higher type recursion, ramification and polynomial time
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Rekursionszahlen und die Grzegorczyk-Hierarchie
• The Structure of Loop Programs and Subrecursive Hierarchies
• The \(\mu\)-measure as a tool for classifying computational complexity
• The realm of primitive recursion

Cited in

(21)

• The fixed point problem of a simple reversible language
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• On the edge of decidability in complexity analysis of loop programs
• scientific article; zbMATH DE number 7471667 (Why is no real title available?)
• scientific article; zbMATH DE number 7215283 (Why is no real title available?)
• Implicit computation complexity in higher-order programming languages
• Programming languages capturing complexity classes
• LISP program-size complexity. II
• The power of non-determinism in higher-order implicit complexity. Characterising complexity classes using non-deterministic cons-free programming
• The Garland measure and computational complexity of stack programs
• Algorithmically broad languages for polynomial time and space
• A Short Introduction to Implicit Computational Complexity
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Machines, Computations, and Universality
• Implicit characterizations of FPTIME and NC revisited
• Computer Science Logic
• Simple programming languages and restricted classes of Turing machines
• On the expressive power of programming languages
• A Refinement of the μ-measure for Stack Programs
• Control structures in programs and computational complexity
• An imperative language characterizing PTIME algorithms

This page was built for publication: On the computational complexity of imperative programming languages

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