paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Equivalence and Conditional Independence in Atomic Sheaf Logic

原子层逻辑(Atomic Sheaf Logic)中的等价与条件独立
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 3/10 · 该论文是纯逻辑与范畴论的形式语义工作,讨论条件独立、概率 sheaf 等概念,与贝叶斯程序分析的理论基础有微弱关联;但未涉及静态分析、LLM/Agent、浮点程序分析或程序分析工程实现,与用户核心研究方向匹配度低。引用 11 inbox
Alex Simpson
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出原子层拓扑语义框架,统一解释变量等价与条件独立,并在经典逻辑中验证基本推理原则。

论文为同时区分变量相等、较粗等价及条件独立的推理场景构建语义基础。作者在原子层拓扑(atomic sheaf topos)中建模这些关系:原子层内蕴的原子等价解释变量等价;生成拓扑的范畴若具备独立拉回系统等额外结构,则可解释条件独立。由此得到原子层拓扑逻辑,并研究其内蕴逻辑诱导的等价与条件独立逻辑;该逻辑是经典逻辑,并验证若干关联两者的基本推理原则。主要实例为有限非空集合间满射范畴上的原子拓扑,其等价与条件独立解释与独立性逻辑的多团队语义一致,等价对应互相包含,但该语义嵌入经典外层逻辑。文末简述概率层与 Schanuel 拓扑(名义集)实例,展示框架通用性。

问题
如何为同时包含变量相等、更粗粒度等价和变量间条件独立的推理系统提供统一的语义基础。
方法
利用原子层拓扑及其内蕴逻辑,通过生成范畴上的独立拉回系统等结构解释条件独立,并研究诱导出的经典逻辑及其推理原则。
评估
在有限非空集合间满射范畴等实例中与独立性逻辑的多团队语义对照,并简述概率层与 Schanuel 拓扑两个额外实例。
原文摘要(Abstract)

We propose a semantic foundation for logics for reasoning in settings that possess a distinction between equality of variables, a coarser equivalence of variables, and a notion of conditional independence between variables. We show that such relations can be modelled naturally in atomic sheaf toposes. Equivalence of variables is modelled by an intrinsic relation of atomic equivalence that is possessed by every atomic sheaf. We identify additional structure on the category generating the atomic topos (primarily, the existence of a system of independent pullbacks) that allows conditional independence to be interpreted in the topos. We then study the logic of equivalence and conditional independence that is induced by the internal logic of the topos. This atomic sheaf logic is a classical logic that validates a number of fundamental reasoning principles relating equivalence and conditional independence. As a concrete example of this abstract framework, we use the atomic topos over the category of surjections between finite nonempty sets as our main running example. In this category, the interpretations of equivalence and conditional independence coincide with those given by the multiteam semantics of independence logic, in which the role of equivalence is taken by the relation of mutual inclusion. A major difference from independence logic is that, in atomic sheaf logic, the multiteam semantics of the equivalence and conditional independence relations is embedded within a classical surrounding logic. At the end of the paper, we briefly outline two other instances of our framework, to demonstrate its versatility. The first of these is a category of probability sheaves, in which atomic equivalence is equality-in-distribution, and the conditional independence relation is the usual probabilistic one. Our other example is the Schanuel topos (equivalent to nominal sets) where equivalence is orbit equality and conditional independence amounts to a relative form of separatedness.

链接与引用

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

BibTeX
@inproceedings{abs-2405-11073,
  title = {Equivalence and Conditional Independence in Atomic Sheaf Logic},
  author = {Alex Simpson},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662132}
}