Bi-Weekly Talk: Marcel Hark: Computing Expected Runtimes for Constant Probability Programs

Wednesday, November 27, 2019, 10:30am

Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9u10

Speaker: Marcel Hark

 

abstract:

We introduce the class of constant probability (CP) programs and show that classical results from probability theory directly yield a simple decision procedure for (positive)almost sure termination of programs in this class. Moreover, asymptotically tight bounds on their expected runtime can always be computed easily. Based on this, we present an algorithm to infer the exact expected runtime of any CP program.