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.FSCD.2020.1
URN: urn:nbn:de:0030-drops-123237
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12323/
Go to the corresponding LIPIcs Volume Portal

Ronchi Della Rocca, Simona ; Dal Lago, Ugo ; Faggian, Claudia

Solvability in a Probabilistic Setting (Invited Talk)

pdf-format:
LIPIcs-FSCD-2020-1.pdf (0.6 MB)

Abstract

The notion of solvability, crucial in the λ-calculus, is conservatively extended to a probabilistic setting, and a complete characterization of it is given. The employed technical tool is a type assignment system, based on non-idempotent intersection types, whose typable terms turn out to be precisely the terms which are solvable with nonnull probability. We also supply an operational characterization of solvable terms, through the notion of head normal form, and a denotational model of Λ_⊕, itself induced by the type system, which equates all the unsolvable terms.

BibTeX - Entry

@InProceedings{ronchidellarocca_et_al:LIPIcs:2020:12323,
  author =	{Simona Ronchi Della Rocca and Ugo Dal Lago and Claudia Faggian},
  title =	{{Solvability in a Probabilistic Setting (Invited Talk)}},
  booktitle =	{5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-155-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{167},
  editor =	{Zena M. Ariola},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12323},
  URN =		{urn:nbn:de:0030-drops-123237},
  doi =		{10.4230/LIPIcs.FSCD.2020.1},
  annote =	{Keywords: Probabilistic Computation, Lambda Calculus, Solvability, Intersection Types}
}

Keywords: Probabilistic Computation, Lambda Calculus, Solvability, Intersection Types
Collection: 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020)
Issue Date: 2020
Date of publication: 28.06.2020

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