paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Fixed-Points for Quantitative Equational Logics

定量等式逻辑的不动点
LICS 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2021匹配度 3/10 · 论文属于定量等式逻辑与不动点的纯形式语义研究,虽与 MDP/Bellman 方程、收敛速率等概率/定量语义有理论关联,但未涉及静态分析、Agentic/LLM、浮点程序分析或贝叶斯程序分析等画像核心方向。引用 0 inbox
Radu Mardare, Prakash Panangaden, Gordon Plotkin
crossref: 2026-09-12

AI 速览

一句话:为定量等式逻辑引入不动点扩展,在定量代数中给出近似相等语义,并刻画收敛速率与 Conway/迭代理论。

本文为定量等式逻辑(quantitative equational logic)发展了不动点扩展。与以往在度量空间中处理精确相等的不动点工作不同,作者采用近似相等这一更适应定量场景的概念,语义建立在一有界完全定量代数上。由此得到一种新的不动点理论:它不仅能求解传统的不动点方程,还能定义向不动点的收敛速率。作者证明该理论是 Conway 理论的定量类比,也是迭代理论的定量类比,并且反映了度量余归纳原理。作为示例,他们研究了 Markov 决策过程的 Bellman 方程。该工作将不动点、代数理论与定量语义统一起来,为定量等式推理提供了新工具。

问题
如何为定量等式逻辑添加不动点,使其在近似相等而非精确相等下成立,并能刻画收敛速率?
方法
在一有界完全定量代数中定义语义,建立定量 Conway 理论与迭代理论,并联系度量余归纳原理。
评估
以 Markov 决策过程的 Bellman 方程作为示例,展示该不动点理论的应用。
原文摘要(Abstract)

We develop a fixed-point extension of quantitative equational logic and give semantics in one-bounded complete quantitative algebras. Unlike previous related work about fixed-points in metric spaces, we are working with the notion of approximate equality rather than exact equality. The result is a novel theory of fixed points which can not only provide solutions to the traditional fixed-point equations but we can also define the rate of convergence to the fixed point. We show that such a theory is the quantitative analogue of a Conway theory and also of an iteration theory; and it reflects the metric coinduction principle. We study the Bellman equation for a Markov decision process as an illustrative example.

链接与引用

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

BibTeX
@inproceedings{paperbot6212,
  title = {Fixed-Points for Quantitative Equational Logics},
  author = {Radu Mardare and Prakash Panangaden and Gordon Plotkin},
  booktitle = {LICS},
  year = {2021},
  doi = {10.1109/lics52264.2021.9470662}
}