Blogs (1) >>
POPL 2019
Sun 13 - Sat 19 January 2019 Cascais, Portugal
Mon 14 Jan 2019 14:30 - 15:00 at Sala III - Probabilistic Systems Chair(s): Justin Hsu

We study the termination problem for nondeterministic probabilistic programs. We consider the bounded termination problem that asks whether the supremum of the expected termination time over all schedulers is bounded. First, we show that ranking supermartingales (RSMs) are both sound and complete for proving bounded termination over nondeterministic probabilistic programs. For nondeterministic probabilistic programs a previous result claimed that RSMs are not complete for bounded termination, whereas our result corrects the previous flaw and establishes completeness with a rigorous proof. Second, we present the first sound approach to establish lower bounds on expected termination time through RSMs.

Mon 14 Jan

14:00 - 15:30: VMCAI 2019 - Probabilistic Systems at Sala III
Chair(s): Justin HsuUniversity of Wisconsin-Madison, USA
VMCAI-201914:00 - 14:30
VMCAI-201914:30 - 15:00
Hongfei FuIST Austria, Krishnendu ChatterjeeIST Austria
VMCAI-201915:00 - 15:30
Stefan Haar, Juraj KolčákLSV, CNRS & ENS Cachan, University Paris Saclay, Loïc Paulevé