paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Expressive Logics for Coinductive Predicates

共归纳谓词的可表达逻辑
LMCS vol.Volume 17, Issue 42021匹配度 3/10 · 该论文属于纯形式语义与共代数逻辑的理论工作,与用户核心关注的 LLM/Agent 驱动的静态分析、浮点程序分析或贝叶斯程序分析没有直接关联;仅在形式化验证/共归纳和行为度量的理论层面有间接联系。引用 7 inbox
Clemens Kupke, Jurriaan Rot
crossref: 2026-09-10

AI 速览

一句话:在共代数上为共归纳谓词建立逻辑完全刻画的一般框架,给出充分条件并实例化相似、发散与行为度量。

经典 Hennessy-Milner 定理表明,像有限的迁移系统中两状态互模拟当且仅当它们满足相同的模态逻辑公式。本文把这一结果从迁移系统推广到共代数,并把互模拟推广为共归纳谓词。作者定义了逻辑对一个共归纳谓词构成完全刻画所需的可靠性与表达性概念,并给出语义层面的充分条件,使得逻辑可用于刻画共归纳谓词。该抽象框架统一处理多种实例:相似性、发散性以及自动机上的行为度量。结果揭示了模态/共代数逻辑与共归纳定义之间的一般联系。

问题
如何将 Hennessy-Milner 式的逻辑完全刻画结果从迁移系统和互模拟推广到共代数上的共归纳谓词。
方法
提出面向共归纳谓词的可靠性与表达性概念,并给出语义层面的充分条件,建立一般性的逻辑刻画定理。
评估
通过相似性、发散性以及自动机上的行为度量等实例说明该框架的适用性;论文属理论研究,未包含实验评估。
原文摘要(Abstract)

The classical Hennessy-Milner theorem says that two states of an image-finite transition system are bisimilar if and only if they satisfy the same formulas in a certain modal logic. In this paper we study this type of result in a general context, moving from transition systems to coalgebras and from bisimilarity to coinductive predicates. We formulate when a logic fully characterises a coinductive predicate on coalgebras, by providing suitable notions of adequacy and expressivity, and give sufficient conditions on the semantics. The approach is illustrated with logics characterising similarity, divergence and a behavioural metric on automata.

链接与引用

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

BibTeX
@article{paperbot1256,
  title = {Expressive Logics for Coinductive Predicates},
  author = {Clemens Kupke and Jurriaan Rot},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 4},
  year = {2021},
  doi = {10.46298/lmcs-17(4:19)2021}
}