2026-08-10T17:31:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12323 2024-03-06T10:49:57Z ddc:004 open_access

Solvability in a Probabilistic Setting (Invited Talk) Ronchi Della Rocca, Simona Dal Lago, Ugo Faggian, Claudia Probabilistic Computation Lambda Calculus Solvability Intersection Types 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Simona Ronchi Della Rocca and Ugo Dal Lago and Claudia Faggian 2020 Is Part Of LIPIcs, Volume 167, 5th International Conference on Formal Structures for Computation and Deduction (FSCD 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2020.1 urn:nbn:de:0030-drops-123237 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2020.1 eng https://creativecommons.org/licenses/by/3.0/legalcode