On the computational complexity of imperative programming languages

DOI10.1016/J.TCS.2003.10.016zbMATH Open1048.03030OpenAlexW2083350000MaRDI QIDQ1827396FDOQ1827396

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

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

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)

Cites Work

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

Cited In (20)

• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implicit computation complexity in higher-order programming languages
• Programming languages capturing complexity classes
• LISP program-size complexity. II
• 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
• The Power of Non-determinism in Higher-Order Implicit Complexity
• Implicit characterizations of FPTIME and NC revisited
• Computer Science Logic
• A Refinement of the μ-measure for Stack Programs
• Simple programming languages and restricted classes of Turing machines
• On the expressive power of programming languages
• Control structures in programs and computational complexity

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)