Survey Lecture: Jürgen Giesl: Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs

Tuesday, May 03, 2022, 4:30pm

Location: Department of Computer Science, Ahornstr. 55, building E2 (no. 2356), ground floor, room: B-IT 5053.2.
We are looking forward to meeting you in person!
Nevertheless, all events are hybrid. To join remotely, please use:
https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09
Meeting ID: 960 0388 5007, Passcode: 273710

Speaker: Jürgen Giesl

 

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.