Congruences for Contextual Graph-Rewriting
Congruences for Contextual Graph-Rewriting
复制标题
上下文图重写的同余
DOI：
--
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
P. Sobocinski
中科院分区：
文献类型：
--
作者：
V. Sassone;P. Sobocinski
我们介绍了一个全面的图重写的操作语义理论。其核心思想是将重写框架重塑为Leifer和Milner的反应式系统。因此，图重写系统与典型的标号转换系统相关联，在该系统上，互模拟等价是关于任意图上下文(图的余弦)的同余。这种结构是从一个更广泛适用的更一般的定理中推导出来的。本文以抽象范畴的形式表示，其主要技术贡献是在任意粘性范畴上的适当的余番范畴中构造了群态相对推出，这是作者在最近的工作中提出的。因此，我们都概括并阐明了由于Ehrig和Konig而通过借用上下文进行重写的情况。
We introduce a comprehensive operational semantic theory of graph rewriting. The central idea is recasting rewriting frameworks as Leifer and Milner's reactive systems. Consequently, graph rewriting systems are associated with canonical labelled transition systems, on which bisimulation equivalence is a congruence with respect to arbitrary graph contexts (cospans of graphs). This construction is derived from a more general theorem of much wider applicability. Expressed in abstract categorical terms, the central technical contribution of the paper is the construction of groupoidal relative pushouts, introduced and developed by the authors in recent work, in suitable cospan categories over arbitrary adhesive categories. As a consequence, we both generalise and shed light on rewriting via borrowed contexts due to Ehrig and Konig.