Contextual Equivalence fo probabilistic languages
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F18%3A00329965" target="_blank" >RIV/68407700:21240/18:00329965 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1145/3236782" target="_blank" >http://dx.doi.org/10.1145/3236782</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3236782" target="_blank" >10.1145/3236782</a>
Alternative languages
Result language
angličtina
Original language name
Contextual Equivalence fo probabilistic languages
Original language description
We present a complete reasoning principle for contextual equivalence in an untyped probabilistic language. The language includes continuous (real-valued) random variables, conditionals, and scoring. It also includes recursion, since the standard call-by-value fixpoint combinator is expressible. We demonstrate the usability of our characterization by proving several equivalence schemas, including familiar facts from lambda calculus as well as results specific to probabilistic programming. In particular, we use it to prove that reordering the random draws in a probabilistic program preserves contextual equivalence. This allows us to show, for example, that (let x = e1 in let y = e2 in e0) =ctx (let y = e2 in let x = e1 in e0) (provided x does not occur free in e2 and y does not occur free in e1) despite the fact that e1 and e2 may have sampling and scoring effects.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
—
Continuities
R - Projekt Ramcoveho programu EK
Others
Publication year
2018
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Journal Proceedings of the ACM on Programming Languages,Volume 2, Issue ICFP
ISBN
—
ISSN
2475-1421
e-ISSN
2475-1421
Number of pages
38
Pages from-to
—
Publisher name
ACM
Place of publication
New York
Event location
St. Louis
Event date
Sep 23, 2018
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—