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

Displayed time zone: Belfast change

14:00 - 15:30
Probabilistic SystemsVMCAI at Sala III
Chair(s): Justin Hsu University of Wisconsin-Madison, USA
14:00
30m
Talk
Syntactic Partial Order Compression for Probabilistic Reachability
VMCAI
Gereon Fox , Daniel Stan , Holger Hermanns Saarland University
14:30
30m
Talk
Termination of Nondeterministic Probabilistic Programs
VMCAI
Hongfei Fu IST Austria, Krishnendu Chatterjee IST Austria
15:00
30m
Talk
Combining Refinement of Parametric Models with Goal-Oriented Reduction of Dynamics
VMCAI
Stefan Haar , Juraj Kolčák LSV, CNRS & ENS Cachan, University Paris Saclay, Loïc Paulevé