paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Relating Apartness and Bisimulation

分离性(Apartness)与互模拟(Bisimulation)的关系
LMCS vol.Volume 17, Issue 32021匹配度 1/10 · 该论文属于余代数、互模拟与并发过程理论的形式语义研究,虽涉及证明系统和形式化,但与用户关注的静态分析、LLM/Agent 交叉、浮点程序分析或贝叶斯程序分析均无直接关联。引用 16 inbox
Herman Geuvers, Bart Jacobs
crossref: 2026-09-10

AI 速览

一句话:从余代数对偶视角关联 apartness 与互模拟,并为弱/分支互模拟建立 apartness 证明系统。

论文研究互模拟(bisimulation)的余代数表述与其对偶概念 apartness 的关系。互模拟是余归纳等价,apartness 表示两元素可被正向区分,即不互模拟;它由最小不动点归纳描述,可用推导规则构成证明系统。作者在关系范畴中用提升函子刻画互模拟,并从初始代数/终结余代数的对偶说明 apartness 是互模拟性的精确对偶。对含 silent τ 步的标号迁移系统,论文定义对应弱互模拟与分支互模拟的 apartness,给出有限推导规则,并把分支互模拟的若干已知性质改写为分支 apartness 加以证明。最后在一般范畴情形展示 apartness 为初始代数、导出归纳原理,并纳入幂集函子以语义化非确定性选择。

问题
如何将互模拟的余归纳等价概念与其对偶的、表示可正向区分的 apartness 概念统一关联,并为 LTS 上弱/分支互模拟提供对应的不互模拟证明系统。
方法
使用余代数、关系范畴与提升函子,将 apartness 刻画为最小不动点/初始代数;对含 τ 步的 LTS 定义弱与分支 apartness 的推导规则,并证明其与相应互模拟互补及相关性质。
评估
评估以范畴论分析与证明系统推导为主,覆盖一般多项式函子、标号迁移系统的弱/分支互模拟,以及幂集函子下的非确定性选择,未涉及实现或实验评估。
原文摘要(Abstract)

A bisimulation for a coalgebra of a functor on the category of sets can be described via a coalgebra in the category of relations, of a lifted functor. A final coalgebra then gives rise to the coinduction principle, which states that two bisimilar elements are equal. For polynomial functors, this leads to well-known descriptions. In the present paper we look at the dual notion of "apartness". Intuitively, two elements are apart if there is a positive way to distinguish them. Phrased differently: two elements are apart if and only if they are not bisimilar. Since apartness is an inductive notion, described by a least fixed point, we can give a proof system, to derive that two elements are apart. This proof system has derivation rules and two elements are apart if and only if there is a finite derivation (using the rules) of this fact. We study apartness versus bisimulation in two separate ways. First, for weak forms of bisimulation on labelled transition systems, where silent (tau) steps are included, we define an apartness notion that corresponds to weak bisimulation and another apartness that corresponds to branching bisimulation. The rules for apartness can be used to show that two states of a labelled transition system are not branching bismilar. To support the apartness view on labelled transition systems, we cast a number of well-known properties of branching bisimulation in terms of branching apartness and prove them. Next, we also study the more general categorical situation and show that indeed, apartness is the dual of bisimilarity in a precise categorical sense: apartness is an initial algebra and gives rise to an induction principle. In this analogy, we include the powerset functor, which gives a semantics to non-deterministic choice in process-theory.

链接与引用

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

BibTeX
@article{paperbot1289,
  title = {Relating Apartness and Bisimulation},
  author = {Herman Geuvers and Bart Jacobs},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 3},
  year = {2021},
  doi = {10.46298/lmcs-17(3:15)2021}
}