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