Bi-Weekly Talk: Fabian Meyer: Termination and Complexity Analysis of Probabilistic Programs

Wednesday, November 10, 2021, 10:30am

Location: Online session

Speaker: Fabian Meyer

 

Abstract: 

Termination and Runtime Complexity are among the most important properties of (probabilistic) programs.
In the first part of the talk, a modular approach to reason about the expected runtime complexity of probabilistic programs is presented.
To that end, we combine bounds on the expected runtime of program parts and bounds on the expected sizes of program variables.

In a second part, we look at a restricted class of simple linear probabilistic programs and the decidability of termination for such programs.
This is work-in-progress.