Probabilistic Böhm Trees and Probabilistic Separation
Author: Thomas Leventis
Paper Information
Title: | Probabilistic Böhm Trees and Probabilistic Separation |
Authors: | Thomas Leventis |
Proceedings: | LICS PDF files |
Editors: | Anuj Dawar and Erich Grädel |
Keywords: | probabilistic lambda-calculus, Böhm trees, observational equivalence, separation |
Abstract: | ABSTRACT. We study the notion of observational equivalence in the call-by-name probabilistic lambda-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. |
Pages: | 10 |
Talk: | Jul 09 17:40 (Session 51E) |
Paper: |