Probabilistic Böhm Trees and Probabilistic Separation
Thomas Leventis · 2018
We study the notion of observational equivalence in the call-by-name probabilistic λ-calculus, where two terms are said observationally equivalent if under any context, their head reductions converge with the same probability. Our goal is to generalise the separation theorem to this probabilistic setting. To do so we define probabilistic Böhm trees and probabilistic Nakajima trees, and we mix the well-known Böhm-out technique with some new techniques to manipulate and separate probability distributions.