Tight polynomial worst-case bounds for loop programs
From MaRDI portal
Recommendations
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
(2)
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)
