paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Categorical liveness checking by corecursive algebras

基于余递归代数的范畴活性检查
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 3/10 · 论文属于形式验证/程序语义的纯理论研究,讨论活性验证的范畴化统一(ranking function 与 ranking supermartingale),与用户核心关注的 PL↔AI、LLM/Agent 静态分析、浮点程序分析或贝叶斯程序分析交叉均无直接关系;仅在最宽泛的程序验证/概率程序终止性分析上与画像有边缘交集。引用 11 inbox
Natsuki Urabe, Masaki Hara, Ichiro Hasuo
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:用余递归代数与余代数模拟,统一范畴化活性验证中的 ranking function 与 ranking supermartingale。

在余代数理论中,终结余代数作为“范畴极大不动点”是核心工具,已有证明方法多面向安全性、互模拟等极大不动点性质;相比之下,活性等极小不动点性质的范畴化证明方法仍不充分。本文朝这一方向迈出一步:为非确定系统中的 ranking function 与概率系统中的 ranking supermartingale 这两类经典活性验证方法寻求范畴公理化。作者发现,合适的答案来自余代数模拟与余递归代数的组合,后者可作为(非)良基性的分类器。由此,论文为以余代数建模的动力系统上的活性性质提供了统一的范畴证明框架。

问题
现有余代数证明理论主要处理安全性、互模拟等最大不动点性质,缺乏对活性等最小不动点性质的范畴化证明方法。
方法
将非确定情形的 ranking function 与概率情形的 ranking supermartingale 作为活性证明方法,用余代数模拟结合可分类(非)良基性的余递归代数进行范畴公理化。
评估
理论性工作;摘要未报告实现或实验,评估体现为对两类经典活性验证方法的统一范畴刻画。
原文摘要(Abstract)

Final coalgebras as “categorical greatest fixed points” play a central role in the theory of coalgebras. Somewhat analogously, most proof methods studied therein have focused on greatest fixed-point properties like safety and bisimilarity. Here we make a step towards categorical proof methods for least fixed-point properties over dynamical systems modeled as coalgebras. Concretely, we seek a categorical axiomatization of well-known proof methods for liveness, namely ranking functions (in nondeterministic settings) and ranking supermartingales (in probabilistic ones). We find an answer in a suitable combination of coalgebraic simulation (studied previously by the authors) and corecursive algebra as a classifier for (non-)well-foundedness.

链接与引用

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

BibTeX
@inproceedings{UrabeHH17,
  title = {Categorical liveness checking by corecursive algebras},
  author = {Natsuki Urabe and Masaki Hara and Ichiro Hasuo},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005151}
}