paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Guarded and Unguarded Iteration for Generalized Processes

广义过程的守卫与非守卫迭代
LMCS vol.Volume 15, Issue 32019匹配度 1/10 · 该论文属于纯范畴论/形式语义,讨论守卫迭代与 Elgot 单子的理论关系,不涉及静态分析、LLM/Agent、浮点或贝叶斯程序分析。与用户研究画像的核心问题几乎没有交集。引用 2 inbox
Sergey Goncharov, Lutz Schröder, Christoph Rauch, Maciej Piróg
crossref: 2026-09-10

AI 速览

一句话:提出抽象守卫性统一守卫迭代与 Elgot 单子,并证明 Elgot 单子恰为抽象守卫迭代单子的迭代同余收缩。

本文研究迭代计算的语义模型。传统迭代单子依赖守卫性来保证递归方程有唯一解,而许多模型允许非守卫迭代,此时解不唯一,也未必是最小或最大不动点,而由拟等式公理刻画,这类单子称为 Elgot 单子。作者为(单子的 Kleisli 范畴)引入抽象守卫性概念,并要求抽象守卫递归方程可解。迭代单子和 Elgot 单子都是其例子:前者按通常守卫性,后者把所有递归定义都视为抽象守卫。主要结果是 Elgot 单子恰好是抽象守卫迭代单子的迭代同余收缩;换言之,非守卫迭代模型可由守卫迭代模型取商得到。

问题
如何为迭代计算建立统一语义框架,将依赖守卫性的唯一解模型与允许非守卫迭代、解不唯一的 Elgot 单子纳入同一范畴论框架?
方法
作者为(Kleisli 范畴中的)单子引入抽象守卫性,要求抽象守卫递归方程可解;迭代单子按通常守卫性实例化,Elgot 单子则把所有递归定义视为抽象守卫。
评估
主要结果以范畴论证明给出:Elgot 单子恰好是抽象守卫迭代单子的迭代同余收缩,从而说明非守卫迭代模型可由守卫迭代模型取商得到。
原文摘要(Abstract)

Models of iterated computation, such as (completely) iterative monads, often depend on a notion of guardedness, which guarantees unique solvability of recursive equations and requires roughly that recursive calls happen only under certain guarding operations. On the other hand, many models of iteration do admit unguarded iteration. Solutions are then no longer unique, and in general not even determined as least or greatest fixpoints, being instead governed by quasi-equational axioms. Monads that support unguarded iteration in this sense are called (complete) Elgot monads. Here, we propose to equip (Kleisli categories of) monads with an abstract notion of guardedness and then require solvability of abstractly guarded recursive equations; examples of such abstractly guarded pre-iterative monads include both iterative monads and Elgot monads, the latter by deeming any recursive definition to be abstractly guarded. Our main result is then that Elgot monads are precisely the iteration-congruent retracts of abstractly guarded iterative monads, the latter being defined as admitting unique solutions of abstractly guarded recursive equations; in other words, models of unguarded iteration come about by quotienting models of guarded iteration.

链接与引用

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

BibTeX
@article{paperbot784,
  title = {Guarded and Unguarded Iteration for Generalized Processes},
  author = {Sergey Goncharov and Lutz Schröder and Christoph Rauch and Maciej Piróg},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 3},
  year = {2019},
  doi = {10.23638/lmcs-15(3:1)2019}
}