Run-time complexity bounds using squeezers

DOI10.1007/978-3-030-72019-3_12MaRDI QIDQ2233463zbMATHOpenAlexFDO

Authors Oren Ish-Shalom, Shachar Itzhaky, Noam Rinetzky, Sharon Shoham

Publication date 18 October 2021

Full work available at URL https://doi.org/10.1007/978-3-030-72019-3_12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Recommendations

• On the inference of resource usage upper and lower bounds
• Resource analysis of complex programs with cost equations
• More precise yet widely applicable cost analysis
• SPEED: precise and efficient static estimation of program computational complexity
• Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis

Cites work

• Algorithmic analysis of programs with well quasi-ordered domains.
• Amortized resource analysis with polynomial potential. A static inference of polynomial bounds for functional programs
• Automatic Inference of Upper Bounds for Recurrence Relations in Cost Analysis
• Complexity and resource bound analysis of imperative programs using difference constraints
• Mechanical program analysis
• Putting the squeeze on array programs: loop verification via inductive rank reduction
• Resource analysis driven by (conditional) termination proofs
• SMT-based model checking for recursive programs
• SPEED: Symbolic Complexity Bound Analysis
• SPEED: precise and efficient static estimation of program computational complexity
• Termination Analysis with Calling Context Graphs
• The size-change principle for program termination
• Well-structured transition systems everywhere!

Cited in

(1)

• SPEED: precise and efficient static estimation of program computational complexity

This page was built for publication: Run-time complexity bounds using squeezers

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