Bi-Weekly Talk: Dominik Meier: Termination of Probabilistic Programs via PTRS

Wednesday, June 16, 2021, 10:30am

Location: Online session

Speaker: Dominik Meier

 

Abstract: 

Using random actions or selections is a very useful ingredient for the development of algorithms. It is typically used to change deterministic algorithms with bad worst-case behavior into efficient random algorithms which produce correct results with a high probability.
These kinds of algorithms can be elegantly expressed as probabilistic programs. Determining termination in the probabilistic case is a difficult problem with often unintuitive results. In the non-probabilistic case, it is possible to convert all kinds of programs into equivalent term rewriting systems and many powerful approaches have been developed to analyze termination of these systems automatically. The talk will deal with the question on how to extend these techniques to the probabilistic case.