String Diagram Rewrite Theory I: Rewriting with Frobenius Structure
String Diagram Rewrite Theory I: Rewriting with Frobenius Structure
复制标题
弦图重写理论一：用Frobenius结构重写
DOI：
10.1145/3502719
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Bonchi F
中科院分区：
文献类型：
--
作者：
Bonchi F
弦图是一种强大而直观的图形语法，起源于理论物理学，后来在对称monoidal范畴的背景下正式化。近年来，它们在计算机科学、物理学、控制论、语言学和生物学等领域的各种计算结构的建模中得到了应用。在其中的一些建议中，系统的转换被建模为图的重写规则。这些发展需要一个数学基础的弦图重写：而重写理论的条款是很好理解的，二维性质的弦图提出了相当多的额外的挑战。这项工作系统化和扩展了一系列最近的会议论文，奠定了这样的基础。作为第一步，我们专注于重写系统的情况下，具有Frobenius代数的弦图解理论。这个共同结构提供了一个比monoidal范畴中的通常概念更宽容的复合概念，并且在并发性，量子理论和电路等领域中找到了许多应用。值得注意的是，这种结构提供了一个确切的对应关系之间的语法概念的字符串图模Frobenius结构和超图的组合结构。我们的工作介绍了一个组合的解释字符串图重写模Frobenius结构的双推出超图重写。我们证明这种解释是健全的和完整的，我们还表明，该方法可以推广到重写模多Frobenius结构。作为一个概念的证明，我们展示了如何从这些结果中得到一个终止策略的相互作用双代数，一个重要的重写理论在量子电路和信号流图的研究。
String diagrams are a powerful and intuitive graphical syntax, originating in theoretical physics and later formalised in the context of symmetric monoidal categories. In recent years, they have found application in the modelling of various computational structures, in fields as diverse as Computer Science, Physics, Control Theory, Linguistics, and Biology.In several of these proposals, transformations of systems are modelled as rewrite rules of diagrams. These developments require a mathematical foundation for string diagram rewriting: whereas rewrite theory for terms is well-understood, the two-dimensional nature of string diagrams poses quite a few additional challenges.This work systematises and expands a series of recent conference papers, laying down such a foundation. As a first step, we focus on the case of rewrite systems for string diagrammatic theories that feature a Frobenius algebra. This common structure provides a more permissive notion of composition than the usual one available in monoidal categories, and has found many applications in areas such as concurrency, quantum theory, and electrical circuits. Notably, this structure provides an exact correspondence between the syntactic notion of string diagrams modulo Frobenius structure and the combinatorial structure of hypergraphs.Our work introduces a combinatorial interpretation of string diagram rewriting modulo Frobenius structures in terms of double-pushout hypergraph rewriting. We prove this interpretation to be sound and complete and we also show that the approach can be generalised to rewriting modulo multiple Frobenius structures. As a proof of concept, we show how to derive from these results a termination strategy for Interacting Bialgebras, an important rewrite theory in the study of quantum circuits and signal flow graphs.
登录
查看更多内容
影响因子：
0.5
作者：
B. Coecke;Dusko Pavlovic;J. Vicary
通讯作者：
B. Coecke;Dusko Pavlovic;J. Vicary
影响因子：
1.1
作者：
L. Bachmair;N. Dershowitz
通讯作者：
N. Dershowitz
Electronic Communications of the EASST Volume 39 ( 2011 ) 图计算模型 第三届国际图计算模型研讨会 ( GCM 2010 ) 超图范畴推出补集的构建
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
M. Heumüller;Salil Joshi;B. König;Jan Stückrath
通讯作者：
Jan Stückrath
DOI：
--
发表时间：
2005
期刊：
影响因子：
--
作者：
R. Rosebrugh;N. Sabadini;R. Walters
通讯作者：
R. Walters
跨度的一些代数定律
DOI：
--
发表时间：
2003
期刊：
RelMiS
影响因子：
--
作者：
R. Bruni;F. Gadducci
通讯作者：
F. Gadducci