FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
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: