Automatic Synthesis of Upper Bounds for Runtime and Size Complexity of Programs
- Speaker: Carsten Fuhs
- Date: Wednesday, 14 October 2015 from 16:00 to 17:00
- Location: Room 151, Birkbeck Main Building
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. Our contributions are implemented in the open-source tool KoAT, and extensive experiments show the performance and power of our implementation in comparison with other tools.