paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Codensity Games for Bisimilarity

面向互模拟的 Codensity 博弈
LICS 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2019匹配度 2/10 · 该论文是程序语义与余代数/范畴论中互模拟博弈的纯理论研究,虽与形式化方法相关,但未涉及用户关注的静态分析、LLM/Agent 交叉、浮点程序分析或贝叶斯程序分析等核心方向。引用 29 inbox
Yuichi Komorida, Shin-ya Katsumata, Nick Hu, Bartek Klin, Ichiro Hasuo
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出基于纤维化与余代数的统一范畴框架,将互模拟类概念的博弈刻画导出为 Codensity 互模拟博弈。

互模拟是进程理论中的核心等价概念,近年来在概率、加权、混合等定量系统中被扩展为互模拟度量、互模拟半范数等。本文关注这类概念的博弈刻画,提出一个统一的范畴框架,使用纤维化(fibration)与余代数(coalgebra)形式化互模拟类概念。作者通过纤维化谓词变换器刻画互模拟,并由此导出 Codensity 互模拟博弈,给出互模拟类概念的一般范畴博弈刻画。该框架涵盖已知的互模拟度量、互模拟半范数,并产生新的互模拟拓扑等概念,说明不同定量互模拟的 Spoiler/Duplicator 博弈可由同一构造统一解释。

问题
如何在概率、加权、混合等定量系统中统一刻画互模拟类概念的 Spoiler/Duplicator 博弈特征,并覆盖已知与新的定量互模拟概念。
方法
使用纤维化与余代数建立范畴框架,通过纤维化谓词变换器刻画互模拟,并导出 Codensity 互模拟博弈这一般性博弈刻画。
评估
以范畴构造与定理证明框架的通用性,并展示其覆盖互模拟度量、互模拟半范数以及新提出的互模拟拓扑等实例。
原文摘要(Abstract)

Bisimilarity as an equivalence notion of systems has been central to process theory. Due to the recent rise of interest in quantitative systems (probabilistic, weighted, hybrid, etc.), bisimilarity has been extended in various ways, such as bisimulation metric between probabilistic systems. An important feature of bisimilarity is its game-theoretic characterization, where Spoiler and Duplicator play against each other; extension of bisimilarity games to quantitative settings has been actively pursued too. In this paper, we present a general framework that uniformly describes game characterizations of bisimilarity-like notions. Our framework is formalized categorically using fibrations and coalgebras. In particular, our characterization of bisimilarity in terms of fibrational predicate transformers allows us to derive what we call codensity bisimilarity games: a general categorical game characterization of bisimilarity. Our framework covers known bisimilarity-like notions (such as bisimulation metric and bisimulation seminorm) as well as new ones (including what we call bisimulation topology).

链接与引用

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

BibTeX
@inproceedings{KomoridaKHKHEH22,
  title = {Codensity Games for Bisimilarity},
  author = {Yuichi Komorida and Shin-ya Katsumata and Nick Hu and Bartek Klin and Ichiro Hasuo},
  booktitle = {LICS},
  year = {2019},
  doi = {10.1109/lics.2019.8785691}
}