UnRAVeL Survey Lecture: Jürgen Giesl: Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs
Tuesday, May 03, 2022
UnRAVeL Survey Lecture: Jürgen Giesl: Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs
- Dr. rer. nat., Universitätsprofessor Jürgen Giesl – Chair for Computer Science 2
Abstract
We present an approach for automatic complexity analysis of integer programs, based on an alternating modular inference of upper runtime and size bounds for program parts. While our approach was originally developed for non-probabilistic programs, we show how we extended it to also infer upper bounds on the expected runtimes of probabilistic integer programs automatically. Moreover, for the non-probabilistic case, we show how recent techniques to improve automated termination analysis of integer programs can be integrated into our approach for the inference of runtime bounds. To evaluate its power, we implemented our approach in a new version of our tool KoAT.