On the computational complexity of imperative programming languages

DOI10.1016/J.TCS.2003.10.016MaRDI QIDQ1827396zbMATHOpenAlexFDO

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)

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

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)