paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Logical Foundations of Quantitative Equality

定量相等的逻辑基础
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 论文属于线性逻辑与范畴语义的理论工作,讨论定量等式、graded modality 和 Lipschitz doctrine,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接交集;仅“定量推理/距离”概念与浮点或概率分析有非常间接的潜在联系。引用 14 inbox
Francesco Dagnino, Fabio Pasquali
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:在 Linear Logic 中把距离视为相等谓词,用 graded modality 建立定量等式的证明系统与 Lipschitz doctrine 语义。

论文旨在为基于距离的定量推理提供逻辑基础,突破传统等价关系只能判断“是否相同”的局限。作者在 Linear Logic 中工作,采用 Lawvere doctrines 的范畴语言,将距离理解为线性逻辑中的相等谓词。通过 graded modalities 给出资源敏感的等式替换规则,使等式具有按距离度量的定量含义。文章提出带定量等式的 (Graded) Linear Logic 演绎演算,并引入 Lipschitz doctrine 作为范畴语义,证明该演算相对此语义的可靠性与完备性。最后给出 Lipschitz doctrine 的泛构造,从度量空间与定量可实现性等来源生成具体模型。

问题
如何用逻辑刻画定量推理中的距离比较,而非仅用等价关系判断对象是否相等。
方法
在线性逻辑中通过 Lawvere doctrines 将距离建模为相等谓词,并用 graded modalities 设计资源敏感的等式替换规则;提出演绎演算与 Lipschitz doctrine 范畴语义。
评估
证明所提演算相对 Lipschitz doctrine 语义的可靠性与完备性,并通过泛构造从度量空间、定量可实现性等构造实例。
原文摘要(Abstract)

In quantitative reasoning one compares objects by distances, instead of equivalence relations, so that one can measure how much they are similar, rather than just saying whether they are equivalent or not. In this paper we aim at providing a logical ground to quantitative reasoning with distances in Linear Logic, using the categorical language of Lawvere’s doctrines. The key idea is to see distances as equality predicates in Linear Logic. We use graded modalities to write a resource sensitive substitution rule for equality, which allows us to give it a quantitative meaning by distances. We introduce a deductive calculus for (Graded) Linear Logic with quantitative equality and the notion of Lipschitz doctrine to give it a sound and complete categorical semantics. We also describe a universal construction of Lipschitz doctrines, which generates examples based for instance on metric spaces and quantitative realisability.

链接与引用

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

BibTeX
@inproceedings{DagninoP22,
  title = {Logical Foundations of Quantitative Equality},
  author = {Francesco Dagnino and Fabio Pasquali},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533337}
}