paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A characterisation of ordered abstract probabilities

有序抽象概率的一种刻画
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文属于纯形式语义/概率代数基础研究,讨论 effect monoid 对实数单位区间的刻画,与用户关注的静态分析、Agentic 程序、LLM 与形式化验证交叉、浮点程序分析或贝叶斯程序分析均无直接关联。引用 5 inbox
Abraham Westerbaan, Bas Westerbaan, John van de Wetering
crossref: 2026-09-12

AI 速览

一句话:通过 effect monoid 刻画实数单位区间,说明其结构可由少量合理假设自然导出。

本文试图解释为何在量子计算等非标准计算模型中,尽管“谓词”等概率论基本概念差异很大,实数单位区间却始终是唯一有用的概率代数。作者研究 effect monoid:它抽象实数单位区间的代数结构,具有仅在 x+y≤1 时定义的部分加法,以及补运算 x↦1-x 构成 effect algebra,并配有结合的(可能非交换的)乘法。有序环的单位区间与布尔代数均为其例子。论文证明,在若干合理假设下,实数单位区间的结构会自然出现,从而给出有序抽象概率的一种代数刻画。

问题
在量子计算等非标准计算模型中,概率论基本概念(如谓词)差异很大,但实数单位区间似乎是唯一有用的概率代数;论文要解释这一现象并刻画有序抽象概率。
方法
论文研究 effect monoid,即实数单位区间代数结构的抽象,包含部分加法 x+y(当 x+y≤1 时定义)、补运算 x↦1-x 以及结合乘法;通过若干合理假设推导出实数单位区间的结构。
评估
属于理论工作,以代数证明和例子分析为主;摘要中给出有序环的单位区间和布尔代数作为 effect monoid 的实例。
原文摘要(Abstract)

In computer science, especially when dealing with quantum computing or other non-standard models of computation, basic notions in probability theory like "a predicate" vary wildly. There seems to be one constant: the only useful example of an algebra of probabilities is the real unit interval. In this paper we try to explain this phenomenon. We will show that the structure of the real unit interval naturally arises from a few reasonable assumptions. We do this by studying effect monoids, an abstraction of the algebraic structure of the real unit interval: it has an addition x + y which is only defined when x + y ≤ 1 and an involution x~1 -- x which make it an effect algebra, in combination with an associative (possibly non-commutative) multiplication. Examples include the unit intervals of ordered rings and Boolean algebras.

链接与引用

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

BibTeX
@inproceedings{paperbot5506,
  title = {A characterisation of ordered abstract probabilities},
  author = {Abraham Westerbaan and Bas Westerbaan and John van de Wetering},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394742}
}