String diagram rewrite theory II: Rewriting with symmetric monoidal structure
String diagram rewrite theory II: Rewriting with symmetric monoidal structure
复制标题
弦图重写理论二：对称幺半群结构重写
DOI：
10.1017/s0960129522000317
复制
发表时间：
2021
影响因子：
0.5
通讯作者：
F. Zanasi
中科院分区：
文献类型：
--
作者：
F. Bonchi;F. Gadducci;A. Kissinger;P. Sobocinski;F. Zanasi
摘要对称monoidal理论（SMTs）以一种使它们适合表达资源敏感系统的方式概括了代数理论，在这种系统中，变量不能随意复制或丢弃。在SMT中，传统的树状术语被弦图所取代，弦图是一种拓扑实体，可以直观地认为是电线和盒子的图。最近，弦图作为一种图形语法越来越受欢迎，可以在不同的领域中推理计算模型，包括编程语言语义学，电路理论，量子力学，语言学和控制理论。在应用中，通常将SMT中出现的方程实现为重写规则是方便的。这就提出了挑战，延长传统的长期重写理论，这已经发展为代数理论，弦图。在本文中，我们开发了一个数学理论的串图改写SMT。我们的方法利用了在本系列的第一篇论文中介绍的某些图的弦图重写和双推出（DPO）重写之间的对应关系。只有当SMT包含Frobenius代数结构时，这种对应才是合理的。在目前的工作中，我们将展示如何建立一个类似的对应任意SMT，一旦一个适当的概念DPO重写（我们称之为凸）被确定。作为概念证明，我们使用我们的方法来显示两个SMT的终止感兴趣：Frobenius半代数和双代数。
Abstract Symmetric monoidal theories (SMTs) generalise algebraic theories in a way that make them suitable to express resource-sensitive systems, in which variables cannot be copied or discarded at will. In SMTs, traditional tree-like terms are replaced by string diagrams, topological entities that can be intuitively thought of as diagrams of wires and boxes. Recently, string diagrams have become increasingly popular as a graphical syntax to reason about computational models across diverse fields, including programming language semantics, circuit theory, quantum mechanics, linguistics, and control theory. In applications, it is often convenient to implement the equations appearing in SMTs as rewriting rules. This poses the challenge of extending the traditional theory of term rewriting, which has been developed for algebraic theories, to string diagrams. In this paper, we develop a mathematical theory of string diagram rewriting for SMTs. Our approach exploits the correspondence between string diagram rewriting and double pushout (DPO) rewriting of certain graphs, introduced in the first paper of this series. Such a correspondence is only sound when the SMT includes a Frobenius algebra structure. In the present work, we show how an analogous correspondence may be established for arbitrary SMTs, once an appropriate notion of DPO rewriting (which we call convex) is identified. As proof of concept, we use our approach to show termination of two SMTs of interest: Frobenius semi-algebras and bialgebras.
弦图重写理论 III：有和没有 Frobenius 的融合
影响因子：
0.5
作者：
Bonchi F
通讯作者：
Bonchi F
用 Frobenius 重写
DOI：
10.1145/3209108.3209137
发表时间：
2018
期刊：
--
影响因子：
--
作者：
Bonchi F
通讯作者：
Bonchi F
弦图重写理论一：用Frobenius结构重写
影响因子：
2.5
作者：
Bonchi F
通讯作者：
Bonchi F