Probabilistic Stable Functions on Discrete Cones are Power Series

被引:7
作者
Crubille, Raphaelle [1 ]
机构
[1] Univ Paris Diderot, Inst Rech Informat Fondamentale, Paris, France
来源
LICS'18: PROCEEDINGS OF THE 33RD ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE | 2018年
关键词
Lambda calculus; Probabilistic computation; Denotational semantics; COHERENCE SPACES;
D O I
10.1145/3209108.3209198
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the category Cstab(m) of measurable cones and measurable stable functions-a denotational model of an higher-order language with continuous probabilities and full recursion [7]. We look at Cstabm as a model for discrete probabilities, by showing the existence of a cartesian closed, full and faithful functor which embeds probabilistic coherence spaces-a fully abstract denotational model of an higher language with full recursion and discrete probabilities [8]-into Cstab(m). The proof is based on a generalization of Bernstein's theorem from real analysis allowing to see stable functions between discrete cones as generalized power series.
引用
收藏
页码:275 / 284
页数:10
相关论文
共 20 条
  • [1] Alur R., 1996, LECT NOTES COMPUTER, V1066
  • [2] [Anonymous], 2014, PROC FOSE 14, DOI DOI 10.1145/2593882.2593900
  • [3] [Anonymous], 2008, P 24 C UNC ART INT
  • [4] Borgström J, 2016, ACM SIGPLAN NOTICES, V51, P33, DOI [10.1145/3022670.2951942, 10.1145/2951913.2951942]
  • [5] Crubille Raphaelle, 2018, PROBABILISTIC STABLE
  • [6] PROBABILISTIC OPERATIONAL SEMANTICS FOR THE LAMBDA CALCULUS
    Dal Lago, Ugo
    Zorzi, Margherita
    [J]. RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2012, 46 (03): : 413 - 450
  • [7] Danos V., 2002, ACM Transactions on Computational Logic, V3, P359, DOI 10.1145/507382.507385
  • [8] Probabilistic coherence spaces as a model of higher-order probabilistic computation
    Danos, Vincent
    Ehrhard, Thomas
    [J]. INFORMATION AND COMPUTATION, 2011, 209 (06) : 966 - 991
  • [9] Ehrhard T, 2018, P ACM PROGRAMMING LA, V2, P59
  • [10] Ehrhard T., 1993, Mathematical Structures in Computer Science, P365