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
Times are displayed in time zone: Greenwich Mean Time : Belfast change

14:00 - 15:30
Probabilistic SystemsVMCAI at Sala III
Chair(s): Justin HsuUniversity of Wisconsin-Madison, USA
14:00
30m
Talk
Syntactic Partial Order Compression for Probabilistic Reachability
VMCAI
14:30
30m
Talk
Termination of Nondeterministic Probabilistic Programs
VMCAI
Hongfei FuIST Austria, Krishnendu ChatterjeeIST Austria
15:00
30m
Talk
Combining Refinement of Parametric Models with Goal-Oriented Reduction of Dynamics
VMCAI
Stefan Haar, Juraj KolčákLSV, CNRS & ENS Cachan, University Paris Saclay, Loïc Paulevé