Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programs
We consider imperative programs that involve both randomization and pure nondeterminism. The central question is how to find a strategy resolving the pure nondeterminism such that the so-obtained determinized program satisfies a given quantitative specification. We show how such strategies can be synthesized using deductive verification techniques. For loop-free programs, the strategies resulting from our weakest precondition-style framework are correct by construction. This extends to loopy programs, provided the loops are equipped with suitable loop invariants - just like in program verification. We show how our technique relates to the well-studied problem of obtaining strategies in Markov decision processes. Finally, we apply our technique to several illustrative case studies.
Thu 18 JanDisplayed time zone: London change
09:00 - 10:20 | Synthesis 2POPL at Kelvin Lecture Chair(s): Michael Hicks Amazon Web Services and the University of Maryland | ||
09:00 20mTalk | Semantic Code Refactoring for Abstract Data Types POPL Shankara Pailoor University of Texas at Austin, Yuepeng Wang Simon Fraser University, Işıl Dillig University of Texas at Austin | ||
09:20 20mTalk | API-driven Program Synthesis for Testing Static Typing Implementations POPL Thodoris Sotiropoulos ETH Zurich, Stefanos Chaliasos Imperial College London, Zhendong Su ETH Zurich | ||
09:40 20mTalk | Programmatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Programs POPL Kevin Batz RWTH Aachen University, Tom Biskup RWTH Aachen University, Germany, Joost-Pieter Katoen RWTH Aachen University, Tobias Winkler RWTH Aachen University | ||
10:00 20mTalk | A Case for Synthesis of Recursive Quantum Unitary Programs POPL Haowei Deng University of Maryland at College Park, Runzhou Tao Columbia University, Yuxiang Peng University of Maryland, Xiaodi Wu University of Maryland |