paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Rule Algebras for Adhesive Categories

Adhesive 范畴上的规则代数
LMCS vol.Volume 16, Issue 32020匹配度 1/10 · 论文属于范畴论/图重写形式语义,研究 DPO 规则代数的结合性与典范表示,不涉及 LLM、Agentic 程序、静态分析、浮点程序分析或贝叶斯程序分析;仅与形式化方法背景有非常间接的联系。引用 22 inbox
Nicolas Behr, Pawel Sobocinski
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:证明 DPO 重写规则的序贯复合在 M-adhesive 范畴中具有结合性,并定义规则代数及其典范表示。

本文研究图结构重写中最经典的双推(DPO)方法,证明规则沿重叠的序贯复合在自然意义下具有结合性,且该结论可在 M-adhesive 范畴这一一般框架中成立,从而补充了经典的 DPO 并发定理。作者在 M-adhesive 范畴及其 finitary 限制、并附加 M-effective unions 条件下定义规则代数;当范畴具有 M-initial 对象时,所得代数还是含单位的。文中进一步给出规则代数的典范表示,说明该概念可用于定义并计算随机 DPO 重写系统中可观测量的统计矩演化。

问题
DPO 重写中规则序贯复合是否具有结合性,以及如何为一般 adhesive 范畴建立规则代数。
方法
在 M-adhesive 范畴及 finitary/M-effective union 条件下构造规则的序贯复合与规则代数,并给出典范表示;存在 M-initial 对象时证明含单位。
评估
以范畴论定理证明和构造进行论证,展示规则代数表示及其在随机 DPO 重写系统统计矩计算中的应用潜力。
原文摘要(Abstract)

We demonstrate that the most well-known approach to rewriting graphical structures, the Double-Pushout (DPO) approach, possesses a notion of sequential compositions of rules along an overlap that is associative in a natural sense. Notably, our results hold in the general setting of $\mathcal{M}$-adhesive categories. This observation complements the classical Concurrency Theorem of DPO rewriting. We then proceed to define rule algebras in both settings, where the most general categories permissible are the finitary (or finitary restrictions of) $\mathcal{M}$-adhesive categories with $\mathcal{M}$-effective unions. If in addition a given such category possess an $\mathcal{M}$-initial object, the resulting rule algebra is unital (in addition to being associative). We demonstrate that in this setting a canonical representation of the rule algebras is obtainable, which opens the possibility of applying the concept to define and compute the evolution of statistical moments of observables in stochastic DPO rewriting systems.

链接与引用

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

BibTeX
@article{abs-1807-00785,
  title = {Rule Algebras for Adhesive Categories},
  author = {Nicolas Behr and Pawel Sobocinski},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 3},
  year = {2020},
  doi = {10.23638/lmcs-16(3:2)2020}
}