Analyzing Runtime and Size Complexity of Integer Programs
Abstract
We present a modular approach to automatic complexity analysis of integer programs. Based on a novel alternation between finding symbolic time bounds for program parts and using these to infer bounds on the absolute values of program variables, we can restrict each analysis step to a small part of the program while maintaining a high level of precision. The bounds computed by our method are polynomial or exponential expressions that depend on the absolute values of input parameters.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 02, 2016
- Source ID
- 10.1145/2866575
Entities
People
- Carsten Fuhs
- Fabian Emmes
- Jürgen Giesl
- Marc Brockschmidt
- Stephan Falke
Organizations
- Air Force Research Laboratory
- German Research Foundation
- Karlsruhe Institute of Technology
- Microsoft
- RWTH Aachen University
- University of London