paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Termination in Convex Sets of Distributions

分布凸集中的终止性
LMCS vol.Volume 14, Issue 42018匹配度 3/10 · 论文属于概率系统形式语义与凸代数理论,讨论终止建模,与用户关注的贝叶斯程序分析存在间接理论关联;但未涉及静态分析、LLM/Agent、浮点程序分析等核心方向,且偏纯理论,缺乏工程实现或工业落地。引用 6 inbox
Ana Sokolova, Harald Woracek
crossref: 2026-09-10

AI 速览

一句话:刻画凸代数单点扩张,为概率系统终止建模提供完整分类,并给出唯一函子性黑洞扩张。

论文研究凸代数(半凸集)的单点扩张问题。凸代数是有限支撑分布单子的 Eilenberg-Moore 代数,可用于建模概率自动机等概率系统;通过增加一个点,可表示系统终止。作者对一类特定凸代数——向量空间中满足附加技术条件的凸子集 D 的凸子集代数——完整描述了所有可能的扩张;该类包含分布凸子集的凸代数,对应非确定性概率自动机。随后又对自由凸代数(建模完全概率系统)给出所有扩张的完整描述。最后证明存在唯一函子性扩张,即所谓黑洞扩张。

问题
如何用凸代数的单点扩张统一建模概率系统中的终止,并分类所有可行扩张。
方法
在有限支撑分布单子的 Eilenberg-Moore 代数框架下,研究凸子集代数与自由凸代数的单点扩张,并分析其函子性。
评估
对指定凸子集类和非确定性概率自动机、自由凸代数/完全概率系统给出完整分类,并证明唯一函子性黑洞扩张的存在。
原文摘要(Abstract)

Convex algebras, also called (semi)convex sets, are at the heart of modelling probabilistic systems including probabilistic automata. Abstractly, they are the Eilenberg-Moore algebras of the finitely supported distribution monad. Concretely, they have been studied for decades within algebra and convex geometry. In this paper we study the problem of extending a convex algebra by a single point. Such extensions enable the modelling of termination in probabilistic systems. We provide a full description of all possible extensions for a particular class of convex algebras: For a fixed convex subset $D$ of a vector space satisfying additional technical condition, we consider the algebra of convex subsets of $D$. This class contains the convex algebras of convex subsets of distributions, modelling (nondeterministic) probabilistic automata. We also provide a full description of all possible extensions for the class of free convex algebras, modelling fully probabilistic systems. Finally, we show that there is a unique functorial extension, the so-called black-hole extension.

链接与引用

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

BibTeX
@article{paperbot354,
  title = {Termination in Convex Sets of Distributions},
  author = {Ana Sokolova and Harald Woracek},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 4},
  year = {2018},
  doi = {10.23638/lmcs-14(4:17)2018}
}