paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Foundations of regular coinduction

正则余归纳的基础
LMCS vol.Volume 17, Issue 42021匹配度 2/10 · 论文研究推理系统的归纳/余归纳/正则解释及其证明论与算法基础,属于纯形式逻辑与语义方向;与用户核心关注的 LLM/Agent 静态分析、浮点程序分析、贝叶斯程序分析及其交叉几乎没有直接关联,仅可能与形式化验证的基础理论有非常微弱的联系。引用 5 inbox
Francesco Dagnino
crossref: 2026-09-10

AI 速览

一句话:为推理系统提出正则解释,统一归纳与余归纳,建立证明论与算法基础,并扩展到 corules。

推理系统用推理规则定义可能递归的谓词,已有归纳与余归纳两种解释。本文研究介于二者之间的 regular 解释:它允许非良基推理,同时保持有限性。作者首先证明基于 regular trees 的自然证明论定义与 rational fixed point 重合,随后给出等价的归纳刻画,并据此设计寻找 judgment 的 regular derivation 的算法。基于这些结果,论文提出 regular coinduction principle 用于证明完备性,以及基于归纳刻画的归纳技术用于证明可靠性。最后,作者将 regular 方法扩展到带 corules 的推理系统,证明这一更灵活的解释同样具有等价的归纳刻画。

问题
如何在归纳与余归纳解释之间建立一种既允许非良基推理又保持有限的 regular 解释,并为其提供证明论与算法基础。
方法
通过 regular trees 与 rational fixed point 建立证明论定义,给出等价归纳刻画与推导搜索算法,并提出 regular 余归纳证明技术;进一步扩展到带 corules 的推理系统。
评估
以理论证明为主:证明 regular 解释的两种定义一致、归纳刻画等价,并证明扩展至 corules 后仍保持等价归纳刻画。
原文摘要(Abstract)

Inference systems are a widespread framework used to define possibly recursive predicates by means of inference rules. They allow both inductive and coinductive interpretations that are fairly well-studied. In this paper, we consider a middle way interpretation, called regular, which combines advantages of both approaches: it allows non-well-founded reasoning while being finite. We show that the natural proof-theoretic definition of the regular interpretation, based on regular trees, coincides with a rational fixed point. Then, we provide an equivalent inductive characterization, which leads to an algorithm which looks for a regular derivation of a judgment. Relying on these results, we define proof techniques for regular reasoning: the regular coinduction principle, to prove completeness, and an inductive technique to prove soundness, based on the inductive characterization of the regular interpretation. Finally, we show the regular approach can be smoothly extended to inference systems with corules, a recently introduced, generalised framework, which allows one to refine the coinductive interpretation, proving that also this flexible regular interpretation admits an equivalent inductive characterisation.

链接与引用

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

BibTeX
@article{paperbot1274,
  title = {Foundations of regular coinduction},
  author = {Francesco Dagnino},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 4},
  year = {2021},
  doi = {10.46298/lmcs-17(4:2)2021}
}