Tight polynomial bounds for loop programs in polynomial space

MaRDI QIDQ5028427zbMATH OpenFDO

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

Publication date 9 February 2022

Full work available at URL https://arxiv.org/abs/2010.02823, https://lmcs.episciences.org/8700

zbMATH Keywords

multivariateworst-casepolynomial boundsasymptotically-tight

Mathematics Subject Classification ID

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

Recommendations

• Tight worst-case bounds for polynomial loop programs
• Tight polynomial worst-case bounds for loop programs
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Computing polynomial program invariants
• Symbolic Loop Bound Computation for WCET Analysis

Cites work

• scientific article; zbMATH DE number 2130678 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 1339873 (Why is no real title available?)
• scientific article; zbMATH DE number 7561611 (Why is no real title available?)
• A characterization of time complexity by simple loop programs
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
• Complexity and resource bound analysis of imperative programs using difference constraints
• Computer Aided Verification
• Computing polynomial program invariants
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• Mechanical program analysis
• On the computational complexity of imperative programming languages
• On the edge of decidability in complexity analysis of loop programs
• Termination of Integer Linear Programs
• Termination of polynomial loops
• The hardness of finding linear ranking functions for lasso programs
• Tight worst-case bounds for polynomial loop programs

Cited in

(2)

• Tight worst-case bounds for polynomial loop programs
• Targeting Completeness: Using Closed Forms for Size Bounds of Integer Programs

This page was built for publication: Tight polynomial bounds for loop programs in polynomial space

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