Tight polynomial worst-case bounds for loop programs
From MaRDI portal
Publication:5114822
Authors: Amir M. Ben-Amram, G. W. Hamilton 
Publication date: 26 June 2020
Full work available at URL: https://arxiv.org/abs/1906.10047
Recommendations
Cites Work
- Efficient algorithms for deciding the type of growth of products of integer matrices
- Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs
- The size-change principle for program termination
- Undecidable problems in unreliable computations.
- Computing polynomial program invariants
- Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
- Verification, Model Checking, and Abstract Interpretation
- Numerical invariants via abstract machines
- An Improved Tight Closure Algorithm for Integer Octagonal Constraints
- Mechanical program analysis
- Factorization forests of finite height
- Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time
- Certifying Polynomial Time and Linear/Polynomial Space for Imperative Programs
- A characterization of time complexity by simple loop programs
- Complexity and resource bound analysis of imperative programs using difference constraints
- Size-Change Abstraction and Max-Plus Automata
- Ranking functions for linear-constraint loops
- On the computational complexity of imperative programming languages
- Factorization Forests
- Deductive verification in decidable fragments with Ivy
- A flow calculus of \(mwp\)-bounds for complexity analysis
- Static complexity analysis of higher order programs
- On the edge of decidability in complexity analysis of loop programs
Cited In (1)
Uses Software
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)
