SPEED: precise and efficient static estimation of program computational complexity

DOI10.1145/1480881.1480898zbMATH Open1315.68095OpenAlexW2109863363MaRDI QIDQ5261512FDOQ5261512

Authors Sumit Gulwani, Krishna K. Mehra, Trishul Chilimbi

Publication date 3 July 2015

Published in Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1480881.1480898

zbMATH Keywords

termination analysiscounter instrumentationquantitative functionssymbolic complexity bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Semantics in the theory of computing (68Q55)

Recommendations

• SPEED: Symbolic Complexity Bound Analysis
• Resource analysis of complex programs with cost equations
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Run-time complexity bounds using squeezers
• Closed-form upper bounds in static cost analysis

Cited in

(36)

• Run-time complexity bounds using squeezers
• Loop summarization using state and transition invariants
• Certified abstract cost analysis
• scientific article; zbMATH DE number 7204445 (Why is no real title available?)
• Deciding fast termination for probabilistic VASS with nondeterminism
• Oracle-guided scheduling for controlling granularity in implicitly parallel languages
• ABC: algebraic bound computation for loops
• A general framework for static profiling of parametric resource usage
• Attribute-based signatures for circuits from bilinear map
• Targeting Completeness: Using Closed Forms for Size Bounds of Integer Programs
• A Coq library for internal verification of running-times
• Efficient Type-Checking for Amortised Heap-Space Analysis
• Control flow refinement and symbolic computation of average case bound
• Computing exact loop bounds for bounded program verification
• A multi-domain incremental analysis engine and its application to incremental resource analysis
• Complexity and resource bound analysis of imperative programs using difference constraints
• Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
• scientific article; zbMATH DE number 7649967 (Why is no real title available?)
• Resource-usage-aware configuration in software product lines
• SPEED: Symbolic Complexity Bound Analysis
• Analysis of executable software models
• A new order-theoretic characterisation of the polytime computable functions
• Convex invariant refinement by control node splitting: a heuristic approach
• Resource analysis of complex programs with cost equations
• More precise yet widely applicable cost analysis
• A flow calculus of \(mwp\)-bounds for complexity analysis
• Time analysis of actor programs
• Implicit computational complexity of subrecursive definitions and applications to cryptographic proofs
• Quantitative interprocedural analysis
• A type-based complexity analysis of object oriented programs
• Selectively-amortized resource bounding
• Semantic foundations for cost analysis of pipeline-optimized programs
• Complexity verification using guided theorem enumeration
• Type-based amortized resource analysis with integers and arrays
• Integrating deployment architectures and resource consumption in timed object-oriented models
• \textsc{ComplexityParser}: an automatic tool for certifying poly-time complexity of Java programs

Describes a project that uses

Uses Software

• SPEED
• aiT
• CSSV

This page was built for publication: SPEED: precise and efficient static estimation of program computational complexity

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