Brockschmidt, M;
Emmes, F;
Falke, S;
Fuhs, C;
Giesl, J;
(2014)
Alternating Runtime and Size Complexity Analysis of Integer Programs.
In: Ábrahám, E and Havelund, K, (eds.)
20th International Conference, TACAS 2014, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2014, Grenoble, France, April 5-13, 2014. Proceedings.
(pp. 140 - 155).
Springer Berlin Heidelberg
![[thumbnail of TACAS14-intcomplexity.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/application_pdf.png) Preview |
PDF
TACAS14-intcomplexity.pdf Available under License : See the attached licence file. Download (453kB) |
Abstract
We present a modular approach to automatic complexity analysis. Based on a novel alternation between finding symbolic time bounds for program parts and using these to infer size bounds on program variables, we can restrict each analysis step to a small part of the program while maintaining a high level of precision. Extensive experiments with the implementation of our method demonstrate its performance and power in comparison with other tools.
| Type: | Proceedings paper |
|---|---|
| Title: | Alternating Runtime and Size Complexity Analysis of Integer Programs |
| Event: | 20th International Conference, TACAS 2014 |
| ISBN-13: | 978-3-642-54861-1 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/978-3-642-54862-8_10 |
| Publisher version: | http://dx.doi.org/10.1007/978-3-642-54862-8_10 |
| Language: | English |
| Additional information: | This is the authors' accepted version of this published paper. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-54862-8_10 |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1455004 |
Archive Staff Only
 |
View Item |
