Tight polynomial worst-case bounds for loop programs

MaRDI QIDQ5114822zbMATH OpenFDO

Authors Amir M. Ben-Amram, G. W. Hamilton

Publication date 26 June 2020

Full work available at URL https://arxiv.org/abs/1906.10047, https://lmcs.episciences.org/6477

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• Tight worst-case bounds for polynomial loop programs
• Tight polynomial bounds for loop programs in polynomial space
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Verification, Model Checking, and Abstract Interpretation

Cites work

• A characterization of time complexity by simple loop programs
• A flow calculus of \(mwp\)-bounds for complexity analysis
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Complexity and resource bound analysis of imperative programs using difference constraints
• Computing polynomial program invariants
• Deductive verification in decidable fragments with Ivy
• Efficient algorithms for deciding the type of growth of products of integer matrices
• Factorization Forests
• Factorization forests of finite height
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• Mechanical program analysis
• Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
• Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs
• Numerical invariants via abstract machines
• On the computational complexity of imperative programming languages
• On the edge of decidability in complexity analysis of loop programs
• Ranking functions for linear-constraint loops
• Size-Change Abstraction and Max-Plus Automata
• Static complexity analysis of higher order programs
• The size-change principle for program termination
• Undecidable problems in unreliable computations.
• Verification, Model Checking, and Abstract Interpretation

Cited in

(1)

• Tight worst-case bounds for polynomial loop programs

Describes a project that uses

Uses Software

• Ivy
• PPL

This page was built for publication: Tight polynomial worst-case bounds for loop programs

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