Bi-Weekly Talk: Fabian Meyer: Termination and Complexity Analysis of Probabilistic Programs
Wednesday, November 10, 2021, 10:30am
Location: Online session
Speaker: Fabian Meyer
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.