paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Thin Coalgebraic Behaviours Are Inductive

薄余代数行为是归纳的
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 1/10 · 该论文属于纯余代数与形式语义理论,讨论薄余代数的归纳刻画、语法与公理化,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接关联,仅在自动机验证背景上存在微弱联系。引用 0 inbox
Anton Chernev, Corina Cîrstea, Helle Hvid Hansen, Clemens Kupke
crossref: 2026-09-12

AI 速览

一句话:证明薄余代数可由初始代数归纳刻画,并给出其语法与单方程公理化。

本文研究解析函子的余代数,这类结构统一建模状态后继可具有对称性的图状系统(如有序元组、循环列表、多重集),其动机来自基于自动机的验证和薄树理论。作者引入薄余代数,即每个状态仅有可数多条无限路径的余代数。核心结果是通过初始代数对薄性给出归纳刻画;为达此目的,他们为薄行为建立了语法,并证明可用单个方程精确刻画两个项表示同一薄行为的条件。最后,作为多项式函子的特例,他们从该语法中重新导出了薄树的 Cantor-Bendixson 秩概念。

问题
如何对解析函子余代数中“薄”行为(每状态仅有可数多条无限路径)给出归纳式、代数化的刻画,并统一处理具有对称性的后继结构。
方法
引入薄余代数,基于初始代数发展薄行为的语法与等式理论,用单个方程刻画项间的行为等价;并针对多项式函子特例恢复 Cantor-Bendixson 秩。
评估
以理论证明为主:通过初始代数与语法导出归纳刻画,并在多项式函子情形与已知的薄树 Cantor-Bendixson 秩结果对照验证。
原文摘要(Abstract)

Coalgebras for analytic functors uniformly model graph-like systems where the successors of a state may admit certain symmetries. Examples of successor structure include ordered tuples, cyclic lists and multisets. Motivated by goals in automata-based verification and results on thin trees, we introduce thin coalgebras as those coalgebras with only countably many infinite paths from each state. Our main result is an inductive characterisation of thinness via an initial algebra. To this end, we develop a syntax for thin behaviours and capture with a single equation when two terms represent the same thin behaviour. Finally, for the special case of polynomial functors, we retrieve from our syntax the notion of Cantor-Bendixson rank of a thin tree.

链接与引用

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

BibTeX
@inproceedings{paperbot8645,
  title = {Thin Coalgebraic Behaviours Are Inductive},
  author = {Anton Chernev and Corina Cîrstea and Helle Hvid Hansen and Clemens Kupke},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00063}
}