On the edge of decidability in complexity analysis of loop programs

DOI10.1142/S0129054112400588MaRDI QIDQ4923290zbMATH OpenFDO

Authors Lars Kristiansen, Amir M. Ben-Amram

Publication date 6 June 2013

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054112400588

zbMATH Keywords

static analysisloop programssubrecursive programming languages

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.) (68N19)

Recommendations

• scientific article; zbMATH DE number 3883587
• The equivalence problem and correctness formulas for a simple class of programs
• Decidability of the analysis problem for dataflow models of programs
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• On the termination of integer loops

Cites work

• A characterization of time complexity by simple loop programs
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Abstract Interpretation Frameworks
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Decidable problems for powerful programs
• Mechanical program analysis
• On the computational complexity of imperative programming languages
• The Complexity of the Equivalence Problem for Simple Programs
• The Equivalence Problem of Simple Programs
• Undecidable problems in unreliable computations.

Cited in

(4)

• scientific article; zbMATH DE number 7471667 (Why is no real title available?)
• scientific article; zbMATH DE number 7215283 (Why is no real title available?)
• scientific article; zbMATH DE number 1678356 (Why is no real title available?)
• Polynomial loops: beyond termination

This page was built for publication: On the edge of decidability in complexity analysis of loop programs

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