paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Combining probabilistic and non-deterministic choice via weak distributive laws

通过弱分配律组合概率选择与非确定性选择
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 3/10 · 论文研究概率与非确定性选择的范畴论形式语义,与用户画像中的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析均无直接交集;仅在概率程序语义这一较远方向上有间接参考价值。引用 28 inbox
Alexandre Goy, Daniela Petrişan
crossref: 2026-09-12

AI 速览

一句话:证明幂集单子到有限分布单子存在弱分配律,导出凸幂集单子,并应用于概率-非确定系统的迹语义与行为等价。

在指称语义中,同时描述概率选择与非确定性选择长期存在组合困难。从范畴论看,其根源是幂集单子到有限分布单子不存在分配律。本文证明了幂集单子到有限分布单子存在弱分配律。由此,作者将熟知的凸幂集单子重新刻画为幂集单子到凸代数范畴的弱提升。该结果给出了概率与非确定性交互系统的统一语义框架,并用于研究此类系统的迹语义与行为等价。

问题
如何从指称语义角度统一组合概率选择与非确定性选择,尤其是克服幂集单子到分布单子不存在分配律这一范畴论障碍。
方法
采用范畴论与单子理论,构造并证明幂集单子到有限分布单子的弱分配律,并将其解释为幂集单子到凸代数范畴的弱提升。
评估
以数学证明和范畴论构造为主要评估方式,未报告实现或基准测试;通过恢复凸幂集单子并展示其在迹语义与行为等价中的应用来体现结果的有效性。
原文摘要(Abstract)

Combining probabilistic choice and non-determinism is a long standing problem in denotational semantics. From a category theory perspective, the problem stems from the absence of a distributive law of the powerset monad over the distribution monad. In this paper we prove the existence of a weak distributive law of the powerset monad over the finite distribution monad. As a consequence, we retrieve the well-known convex powerset monad as a weak lifting of the powerset monad to the category of convex algebras. We provide applications to the study of trace semantics and behavioral equivalences of systems with an interplay between probability and non-determinism.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5535,
  title = {Combining probabilistic and non-deterministic choice via weak distributive laws},
  author = {Alexandre Goy and Daniela Petrişan},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394795}
}