License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2018.16
URN: urn:nbn:de:0030-drops-96835
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9683/
Go to the corresponding LIPIcs Volume Portal

Clairambault, Pierre ; Paquet, Hugo

Fully Abstract Models of the Probabilistic lambda-calculus

pdf-format:
LIPIcs-CSL-2018-16.pdf (0.6 MB)

Abstract

We compare three models of the probabilistic lambda-calculus: the probabilistic Böhm trees of Leventis, the probabilistic concurrent games of Winskel et al., and the weighted relational model of Ehrhard et al. Probabilistic Böhm trees and probabilistic strategies are shown to be related by a precise correspondence theorem, in the spirit of existing work for the pure lambda-calculus. Using Leventis' theorem (probabilistic Böhm trees characterise observational equivalence), we derive a full abstraction result for the games model. Then, we relate probabilistic strategies to the weighted relational model, using an interpretation-preserving functor from the former to the latter. We obtain that the relational model is also fully abstract.

BibTeX - Entry

@InProceedings{clairambault_et_al:LIPIcs:2018:9683,
  author =	{Pierre Clairambault and Hugo Paquet},
  title =	{{Fully Abstract Models of the Probabilistic lambda-calculus}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9683},
  URN =		{urn:nbn:de:0030-drops-96835},
  doi =		{10.4230/LIPIcs.CSL.2018.16},
  annote =	{Keywords: Game Semantics, Lambda-calculus, Probabilistic programming, Relational model, Full abstraction}
}

Keywords: Game Semantics, Lambda-calculus, Probabilistic programming, Relational model, Full abstraction
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI