On the computational complexity of imperative programming languages

DOI10.1016/j.tcs.2003.10.016zbMath1048.03030OpenAlexW2083350000MaRDI QIDQ1827396

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Turing machines and related notions (03D10)

Related Items (12)

A Short Introduction to Implicit Computational Complexity ⋮ Algorithmically broad languages for polynomial time and space ⋮ Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time ⋮ The Power of Non-determinism in Higher-Order Implicit Complexity ⋮ Unnamed Item ⋮ The fixed point problem of a simple reversible language ⋮ The Garland Measure and Computational Complexity of Stack Programs ⋮ A Refinement of the μ-measure for Stack Programs ⋮ ON THE EDGE OF DECIDABILITY IN COMPLEXITY ANALYSIS OF LOOP PROGRAMS ⋮ Control structures in programs and computational complexity ⋮ Unnamed Item ⋮ Implicit characterizations of FPTIME and NC revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The realm of primitive recursion
• A new recursion-theoretic characterization of the polytime functions
• Augmented loop languages and classes of computable functions
• Function-algebraic characterizations of log and polylog parallel time
• Higher type recursion, ramification and polynomial time
• The \(\mu\)-measure as a tool for classifying computational complexity
• Classes of Predictably Computable Functions
• The Structure of Loop Programs and Subrecursive Hierarchies
• Ranking Primitive Recursions: The Low Grzegorczyk Classes Revisited
• Hierarchies of Primitive Recursive Functions
• Rekursionszahlen und die Grzegorczyk-Hierarchie

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