Rewriting modulo symmetric monoidal structure
Rewriting modulo symmetric monoidal structure
复制标题
重写模对称幺半群结构
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
F. Zanasi
中科院分区：
文献类型：
--
作者：
F. Bonchi;F. Gadducci;A. Kissinger;P. Sobocinski;F. Zanasi
字符串图是一种功能强大且直观的图形语法，用于表示对称么半群范畴(SMC)。它们在计算机科学中发现了许多应用，并在物理和控制理论等其他领域变得越来越相关。在许多这样的方法中，图的方程理论扮演着重要的角色，通常作为重写规则来定位和应用。本文为这种形式的改写奠定了全面的基础。我们将图组合地解释为类型超图，并建立了一方面以SMCS定律为模的图重写与超图的双推(DPO)重写之间的精确对应，该重写受称为凸性的健全条件的约束。这一结果依赖于一个更一般的刻画定理，其中我们证明了类型化超图DPO重写相当于以选择的特殊Frobenius结构为模的SMC法则的图重写。我们用非对易双么半群理论的终止性证明来说明我们的方法。
String diagrams are a powerful and intuitive graphical syntax for terms of symmetric monoidal categories (SMCs). They find many applications in computer science and are becoming increasingly relevant in other fields such as physics and control theory.An important role in many such approaches is played by equational theories of diagrams, typically oriented and applied as rewrite rules. This paper lays a comprehensive foundation for this form of rewriting. We interpret diagrams combinatorially as typed hypergraphs and establish the precise correspondence between diagram rewriting modulo the laws of SMCs on the one hand and double pushout (DPO) rewriting of hypergraphs, subject to a soundness condition called convexity, on the other. This result rests on a more general characterisation theorem in which we show that typed hypergraph DPO rewriting amounts to diagram rewriting modulo the laws of SMCs with a chosen special Frobenius structure.We illustrate our approach with a proof of termination for the theory of non-commutative bimonoids.
分类量子力学中的强互补性和非定域性
DOI：
10.1109/lics.2012.35
发表时间：
2012
期刊：
--
影响因子：
--
作者：
Coecke B
通讯作者：
Coecke B