New Approaches for Almost-Sure Termination of Probabilistic Programs

Mingzhang Huang, Hongfei Fu, Krishnendu Chatterjee

We study the almost-sure termination problem for probabilistic programs. First, we show that supermartingales with lower bounds on conditional absolute difference provide a sound a…