计算机科学家的弦图导论
An Introduction to String Diagrams for Computer Scientists
https://www.cambridge.org/core/books/an-introduction-to-string-diagrams-for-computer-scientists/3CDAF8F57D2299F0EACA3354E9757CFD
![]()
![]()
![]()
摘要:
弦图是一种强大的图形语言,用于表示计算机科学、物理学和语言学等多个不同科学领域中的计算现象。弦图的吸引力在于其多面性:它们为复杂的科学思想提供简单、直观的视觉表示,同时也允许严格的数学处理。弦图起源于范畴论,此后已发展成为一种多用途的形式化工具,远远超出了其抽象代数根源,并为其研究提供了替代性的切入点。本Element从计算机科学的角度提供了对弦图的可访问介绍。作者没有从范畴论概念出发,而是借鉴形式语言理论的直觉,将弦图视为一种具有自身语义的语法。他们综述了基本理论,概述了基本原理,并重点介绍了弦图在不同领域的现代应用。本书也可在Cambridge Core上以开放获取方式获得。
关键词:弦图,幺半范畴,语义学,编程语言,范畴论
1 支持弦图的理由
程序的代数结构
![]()
![]()
计算的图形模型
正如我们所见,通过归纳定义的语法来定义形式语言带来了明显的益处。然而,并非所有计算现象都能通过这种形式化方法被充分刻画。例如,想一想在数字控制器中流动的数据。在这种模型中,信息以复杂的方式在各组件间传播,需要对资源如何处理施加约束。例如,某个门电路可能一次只能接收一定数量的数据,或者可能发生死锁。复杂的交互形式,例如量子过程中的纠缠,或概率系统中随机变量之间的条件(不)独立性,也需要一种能够清晰且富有表现力地捕捉组件间资源交换的语言。
历史上,科学家们采用图形形式化方法来恰当地可视化并推理这些现象。图提供了一种简单的图示表示,展示信息如何在基于组件的系统中流动,而这些若用传统的文本记号来编码则会很困难。这些形式化方法的著名例子包括电气和数字电路、量子电路、信号流图(用于控制理论)、Petri网(用于并发理论)、概率图模型(如贝叶斯网络和因子图),以及神经网络。(见图1.1。)
![]()
另一方面,与语法定义的形式语言相比,图形模型有明显的缺点。我们对组合式、图状结构进行数学推理的能力是有限的。我们通常缺少一种形式化理论,来说明如何将这些模型分解为更简单的组件,以及如何将它们组合在一起以创建更复杂的模型。简而言之,图形模型通常被视为铁板一块的整体,而非模块化的实体。反过来,这意味着我们不能像对待标准程序语法那样,通过对模型结构进行归纳来证明它们的性质。程序分析的关键特性,例如组合语义的定义,以及对支撑模型行为的代数结构的研究,在适应图形形式化方法时会面临重大障碍。
弦图:两全其美
弦图起源于范畴论的抽象数学框架,作为一种描述幺半范畴中态射的图示记号。然而,在过去三十年间,它们在计算机科学及相关领域中的使用显著扩展,远远超出了其最初的目的。弦图之所以如此吸引人,在于其双重性质。就像图形模型一样,它们是一种图示形式化方法:我们可以像对待图一样,用节点和边来指定和推理弦图。然而,就像编程语言一样,弦图也可以被视为一种形式语法;我们可以把它们看作由基本组件(类似于电路的逻辑门,但比那要一般得多)组成,并通过语法定义的运算进行组合。
值得注意的是,将弦图理解为语法定义的对象并不需要切换到另一种(文本)形式化方法——图形表示本身就是由语法构成的(图1.2)。幺半范畴理论为如何在弦图的组合视角与语法视角之间进行切换提供了严格的形式化,同时也为研究其语义和代数性质提供了丰富的框架。的确,就像编程语言一样,我们可以将语义以组合方式分配给弦图,即作为范畴之间的函子。这为我们提供了一种模块化的方式来指定和推理它们所表示模型的行为。
![]()
当代研究中的弦图
得益于其多用途性,弦图正日益被各个研究领域的科学家采纳为一种推理工具。我们可以识别出使用弦图的两大主要趋势:作为一种对图形模型进行语法推理的方式,以及作为一种以更具视觉性、对资源更敏感的方式对(文本)形式语言进行推理的方式。
在第一种趋势中,弦图方法使得那些此前缺乏这些特性的图形形式化方法能够采用组合语义和代数推理。例子包括Petri网[16]、线性动力系统[6, 20, 55]、量子电路[109]、电路[11]以及贝叶斯网络[51, 57, 75]等(见图1.3)。除了为这些模型提供统一的数学视角外,弦图还展示了产生可切实应用、且能用于工业规模成果的能力。一个令人信服的例子是ZX演算,这是一种推广了量子电路的图解语言。它现在已成为开发最先进量子电路优化算法[48]的基础,并正被处理量子计算的公司广泛采用。
![]()
作为第二种趋势的例子,弦图在针对高阶函数式语言的编译器[95]的开发中,以及在一种可证明可靠的逆向模式自动微分算法[3]中,发挥了重要作用。在这两个例子中,弦图都作为一种中间形式化方法,位于高层编程语言与底层实现之间。作为前者,它们可以在语法上进行操作。作为后者,它们明确地表示信息传播以及系统的其他结构性质(见图1.4)。
大纲
本导论提供了弦图及其应用的基本概述。第2节介绍弦图(最常见的变体)的形式语法、操作它们的规则以及等式理论。第3节展示弦图如何也可以被视为某种(超)图,从而为这些对象提供一种等价的组合视角。在第4节中,我们考虑弦图的其他变体,它们对应于不同的语法,并可以以更宽松或更严格的方式进行操作。第5节解释如何为弦图赋予语义;我们涵盖常见的语义示例及其等式性质。第6节包含指向本导论中未详细涵盖的不同趋势的指引。最后,第7节是一份非详尽的弦图应用列表,涵盖计算机科学内外。
范畴论的使用被保持在最低限度,并且我们尽可能优先考虑直觉而非技术细节。为了方便读者,我们附上了一个包含范畴论最基本定义的附录。然而,不应将其视为该主题的入门介绍,对此我们推荐[86]。
2 作为语法的弦图
![]()
![]()
![]()
条款
![]()
![]()
在这里,我们可以将线上方的项列表视为形成规则结论(线下方)中的项所需的假设,前提是满足附带条件。对于对称幺半图,规则如下。
![]()
2. 其次,每个内置运算(下方从左到右依次为:恒等、对称和空)也产生一个项:
![]()
3. 对于归纳步骤,可以通过顺序地(左)或并行地(右)组合两个项来构建一个新项。请注意,对于顺序组合,最左边项的输出需要与最右边项的输入相匹配。对于并行组合,没有这种要求,并且所得的项其输入(输出)是由起始项的输入(输出)所构成的字的拼接。
![]()
![]()
![]()
![]()
![]()
“态”、“效应”和“标量”这些名称源于这类弦图在量子理论中所扮演的角色[35]。
从项到弦图
项与弦图并不完全相同。一旦我们考虑更精细的项,就会意识到前面的定义要求我们在图上附加额外的记号,以追踪我们应用不同组合形式的顺序。例如,(2.2)是来自例2.1中签名的一个项。
![]()
它表示一个非常简单的协议:从栈中弹出两个值,删除第二个值,将第一个值加一,然后将其推回栈中。为了可读性,我们仅保留了外部对象标签。其完整的推导树见图2.1。请注意,虚线框的括号结构完全指定了相应的推导树。
![]()
![]()
![]()
![]()
![]()
这种表示现在是无歧义的,因为(2.3)中的公理意味着,围绕(2.4)各组成部分放置虚线框的任何方式都会产生等价的 Σ Σ-项。例如,以下两个加括号的项作为弦图是等价的:
![]()
这里有一个重要的微妙之处:如果在形式上,弦图是由(2.3)的定律取商后的项的等价类,那么描绘一个弦图的方式并不是唯一的。换句话说,图形表示(即使没有虚线框)处于项与弦图之间,因为它无法区分某些等价的项。在某些情况下,这种描绘吸收了SMC的定律,例如,对于交换律的等式两边:
![]()
在其他情况下,我们绘制它们的方式会区分在(2.3)的定律下等价的弦图。例如,考虑
![]()
这个等式可以被视为带有恒等连线的交换律(2.5)的一个实例,或者是恒等连线单位性的一个推论,它允许我们随意拉伸连线。
一个相关的点是,弦图并不区分不同的连线编织方式,即使我们的绘图会区分:(2.3)的定律保证了,任何两个完全由连线交叉构成、且交叉相同数量连线的弦图,只要它们定义了连线的相同排列,它们就是相等的。如果说其他规则是结合律的二维版本,那么连线交叉公理就是交换律的二维推广。在普通代数中,当我们有一个可交换且结合的二元运算时,我们可以用其元素的任意顺序来书写乘积:\(abc = bac = acb\)。对于弦图而言,盒子的垂直并置并非严格可交换的;然而,我们允许盒子跨过连线移动,这是次优的选择:
![]()
(我们邀请读者将此作为他们图解推理的第一个练习。)此外,我们需要追踪盒子是如何连线的,但只有连线的特定排列才是重要的,而不是我们是如何构造它的。回到我们的栈机例子,以下是等价的弦图:
![]()
虽然这种情况乍看之下可能略显令人困惑,但这些例子表明,在实践中,弦图(作为等价类)与我们如何描绘它们之间的区别是无害的。由(2.3)的等式所捕捉的拓扑变换被设计成直观的。它们通常被以下口号所概括:*只有连通性才是重要的*。经验法则是,任何保留了盒子之间连通性且不要求我们向后弯折连线的形变,都将给出两个等价的弦图。
最后,请记住,将连线连接到盒子上的连接点是有序的,因此以下两个弦图是不等价的:
![]()
在代数中,由签名生成的项的集合(不附加任何额外的运算或等式)通常被称为该签名上的自由结构。弦图的图解语言带有一种相关的自由结构概念:给定签名上的自由对称幺半范畴(SMC)。
此时,更偏向数学的读者可能会提出异议,认为我们仍然没有严格定义什么是SMC。有些循环地说,我们可以将SMC定义为一个我们可以在其中解释弦图的结构!不那么同义反复地说,它是一个带有一个额外运算——幺半积——的范畴,该运算作用于对象和态射上,并满足(2.3)中所示的定律。为了不用弦图来陈述它们,我们需要为组合和幺半积引入显式记号。我们在下面的定义中这样做。请注意,我们假设读者具备范畴的基本知识。该定义及相关概念可以在附录中找到。
![]()
![]()
![]()
正如弦图一样,给定态射的符号记号写法有多种。事实上,因为弦图将SMC的某些定律吸收到了记号中,所以一个给定态射的符号写法通常比它的图解表示更多。
![]()
![]()
![]()
![]()
对称幺半函子
每当我们定义一个新的数学结构时,引入它们之间相应的映射概念是一种好习惯。对于SMC,这就是对称幺半函子的概念。我们在第5节为弦图赋予语义解释时将需要它。
![]()
![]()
![]()
![]()
![]()
事实上,这个SMC也等价于有限集及其间双射构成的非严格SMC,其幺半积为不交并。建立这种等价性也是直接的,但需要我们在每个有限集上固定一个全序。
这个例子只是对一个将在第5节中进一步展开的思想的初步体验,该节专门讨论弦图的语义——即解释。
2.1 添加等式
![]()
![]()
![]()
2.2 常见的等式理论
有些理论在文献中频繁出现。许多作者假定读者熟悉隐藏在“幺半群”、“余幺半群”、“双幺半群/双代数”或“Frobenius幺半群/代数”等术语背后的公理,以及所有这些理论之间如何相互关联。因此,熟练掌握它们是有价值的,特别是在试图将图解证明中的常规步骤与关键步骤区分开来时。本节描述了几个最常见的例子。
![]()
![]()
观察到我们刚刚用连线替换了变量,并用图解生成元替换了代数运算。正如在普通代数中一样,如果两个项/图可以通过应用这三个等式的某个序列而从其中一个得到另一个,那么它们就是相等的(回顾注2.11)。
![]()
![]()
![]()
![]()
![]()
![]()
![]()
作为语法糖来指代 ⊸ 的多次应用。出于这个原因,读者也可能遇到这样的图解证明:它们将幺半群运算应用于同一组元素的不同方式视为相同,就像精通普通代数的实践者通常会毫无歧义地省略括号一样。
例2.14(余幺半群)。与代数语法不同,弦图允许余元数不同于1的运算,这表现为多个(或没有)右边界连线。因此,可以将幺半群理论的生成元和公理翻转,以获得余幺半群的对称幺半理论!不出所料,它由带有单个对象(因此在图中我们将其省略)的签名、两个分别称为余乘法和余单位的生成元来表示:
![]()
![]()
![]()
一个余幺半群进一步是余交换的,如果
![]()
![]()
![]()
出于这个原因,从图解的角度来看,代数理论(或Lawvere理论,它们的范畴论表亲,见[74])总是带有一种选定的余交换余幺半群结构[23],尽管这种结构并未出现在通常变量的符号记号中(后者转而依赖无限供应的唯一名称来作为变量的标识符)。我们将在注5.2中回到这一点。
注2.15(对称幺半理论与线性)。就像普通代数中的幺半群一样,对称幺半理论中的幺半群或余幺半群可以具有附加性质。我们已经遇到了交换幺半群和余交换余幺半群。然而,对称幺半理论与代数理论之间的类比隐藏了一个重要的微妙之处:如果在前者中,连线扮演变量的角色,那么它们必须被恰好使用一次。与普通代数中的变量不同,我们不能多次使用连线,也不能完全不使用它们!这一限制——被称为资源敏感性——是图解语法的一个重要特征。不涉及变量多次使用的性质可以完全类似地指定,正如我们在交换性中所看到的那样。在等号两边都恰好使用每个变量一次的公式被称为线性公式。然而,非线性公式无法直接翻译到图解语境中。例如,提及幂等幺半群的对称幺半理论是毫无意义的:幂等幺半群是满足
的那些幺半群。确实,即使是陈述幂等性公理,也需要具备复制连线的能力。正如我们将看到的,幂等性也可以用图解方式表达,但它是作为一个比幺半群更复杂的代数结构的性质;它可以表述为双幺半群的性质,这是我们的下一个例子。这个例子是一个更一般模式的实例,该模式允许我们恢复普通代数语法的资源不敏感性。我们将在第4.2.5节中更系统地探讨这种对应关系。
幺半群和余幺半群各自的理论可以以不同方式相互作用,正如接下来的两个例子所说明的那样。在这里的“相互作用”是指,当考虑一个同时包含幺半群生成元和余幺半群生成元及其各自理论的签名时,人们可以施加不同的等式。
例2.16(余/交换双幺半群)。一种可能的理论公理化了一种称为双幺半群的结构。它由幺半群和余幺半群的生成元来呈现:
![]()
连同它们各自的公理,以及以下额外的四个等式:
![]()
直观地说,这些等式可以被视为同一条一般原则的实例:每当幺半群的生成元之一与余幺半群的生成元之一进行水平组合时,它们就会彼此穿过,产生各自的多个副本。这是分配律的一种二维形式。例如,当单位元遇到余乘法时,后者复制前者;当乘法遇到余乘法时,它们相互复制(注意这如何需要对称性,即交叉连线的能力)。利用前几个例子中引入的广义幺半群和余幺半群运算,我们可以制定一个广义双幺半群公理模式,捕捉所有四个公理(以及更多):
![]()
那么,对于每侧连线数量为零或二的特定情况,可以恢复这四条定义性公理。
正如我们在例2.14中已经提到的,余幺半群可以模拟普通代数中变量的多次使用。因此,在双幺半群的语境下,我们可以陈述涉及同一变量出现次数多于或少于一次的普通等式。例如,一个双幺半群是幂等的,当它满足以下附加等式时,该等式清楚地将通常的 m ( x , x ) = x 翻译成了一个图解公理:
![]()
![]()
这个等式为幺半群和余幺半群结构的乘法与余乘法相互作用提供了一种替代方式:与双幺半群的情况不同,这一次它们不会相互复制,而只是从彼此旁边滑过,无论是在哪一侧。这是一个根本性的差异,事实上,它被证明与双幺半群的公理是不相容的。我们将在第4.2.10节中更仔细地考察这种不相容性。
读者可能会在文献中遇到这条公理的其他版本,例如:
![]()
在其他公理(即余单位律和余结合律)存在的情况下,这两个等式可以从(2.7)推导出来。为了体会图解推理,让我们来证明它:
![]()
起初,弦图初学者可能会觉得很难内化构成诸如Frobenius幺半群理论的所有定律。在证明某些等式时,并不总是清楚在哪个步骤应用哪条公理才能达到期望的目标,并且很容易被所有可用的选择弄得不知所措。然而,在一些良好的情况下,正如我们在(余)幺半群中所看到的那样,存在一些高层原则,允许我们简化推理并更清楚地看到前面的关键步骤。例如,在对结合律保持沉默的意义下进行推理(即默认结合律成立)在足够练习后会成为第二天性,人们不再将(余)乘法的两个不同复合视为不同的对象。
![]()
![]()
这里我们使用省略号来表示遵循相同模式的任意大的复合。换句话说,在Frobenius幺半群理论中,连通弦图唯一相关的结构是它具有的左连线和右连线的数量,以及从任何左腿到任何右腿存在多少条路径(即在刚才描绘的标准形式中有多少个环)。这一观察有时被称为*蜘蛛定理*,它为引入我们称为蜘蛛的广义顶点作为语法糖提供了依据:
![]()
其中自然数
表示刚才所描绘的标准形式中的内环数量。现在,Frobenius幺半群的所有定律都可以被总结为一个方便的公理模式:
![]()
其中 k 是连接等式左侧两只蜘蛛的中间连线的数量。因此,对于任何复杂的弦图,我们只需要追踪开放连线和环的数量;这极大地减轻了推理该理论时的心理负担。
满足以下幂等性公理的Frobenius幺半群在文献中经常出现:
![]()
在这种情况下,该Frobenius幺半群被称为*特殊的*(有时也称为*可分的*)。在此情况下,蜘蛛定理给出的标准形式会进一步简化,因为我们现在可以忽略内环:
![]()
在特殊Frobenius幺半群理论中,任何连通弦图唯一相关的结构就是其左连线和右连线的数量。因此,我们可以引入相同的语法糖,省略蜘蛛上方的环数。蜘蛛融合模式也进一步简化,因为我们不再需要追踪连接两个融合蜘蛛的腿的数量。
例2.18(特殊且交换的Frobenius幺半群)。交换且特殊的Frobenius幺半群在文献中非常常见,因为它们是在推理关系时自然会出现的一种代数结构(正如我们在第5节研究弦图语义时将看到的那样)。我们在此总结完整的等式理论以供将来参考:
![]()
![]()
例2.19。一个特殊Frobenius幺半群如果还满足以下公理,有时被称为超特殊的(extra-special):
![]()
![]()
读者会经常遇到我们在此涵盖的这些理论,作为更复杂的图解演算的构建块,这些演算旨在捕捉不同种类的现象。例如,ZX演算——一种推广了量子电路的理论(见第7节)——包含的不是一个,而是两个特殊交换Frobenius幺半群,通常分别用红点和绿点表示。它们相互作用形成两个双幺半群:绿幺半群与红余幺半群构成一个双幺半群,红幺半群与绿余幺半群也是如此。起初,这看起来似乎有太多结构需要吸收,但很快,人们就会学会使用蜘蛛定理来思考单色弦图,从而使得大部分复杂性来自两种颜色的相互作用。即使如此,我们在例2.16中看到的广义双幺半群定律也大有帮助。事实上,ZX演算的现代表述更倾向于使用任意元数和余元数的蜘蛛作为运算,并使用蜘蛛融合规则作为公理。引人注目的是,非常相似的等式理论可以在不同科学领域的许多不同应用中普遍地找到:似乎在我们对计算现象进行建模的方式中,幺半群-余幺半群对之间的相互作用具有某种根本性的东西。我们将在第7节中看到几个示例应用。
注2.20(分配律)。值得注意的是,双幺半群的等式(例2.16)和Frobenius幺半群的等式(例2.17)都描述了幺半群与余幺半群的相互作用,尽管它们以不同的方式进行。一种表述方式是借助因子分解:双幺半群定律允许我们将任何弦图分解为所有余幺半群生成元都位于幺半群生成元之前的图,如(2.6)中那样;相反,Frobenius定律产生一种幺半群后跟余幺半群的因子分解,如蜘蛛定理中那样。更抽象地说,这两种等式理论可以被描述为涉及幺半群和余幺半群的分配律的不同规范。分配律在代数中是一个熟悉的概念:主要的例子是环,其等式描述了幺半群在阿贝尔群上的分配性。在对称幺半理论的语境中,分配律甚至更为强大,因为它们可以用来研究具有任意余元数生成元的理论之间的相互作用,例如余幺半群、Frobenius幺半群等等。对对称幺半理论分配律的系统研究由Lack[84]开创,并在较近期的著作[22, 23, 116]中得到了扩展。将理论理解为分配律的结果,使我们能够获得其弦图的因子分解定理,例如(2.6)和蜘蛛定理。此外,它还为语法指定的弦图理论提供了关于更具体表示(即语义)的洞见——这是我们将在第5节探讨的主题。例如,上述ZX演算的无相位片段可以通过两个双幺半群之间的分配律来理解。这一观察对于证明无相位ZX演算的自由模型是线性子空间范畴[19]至关重要。我们建议读者参阅[116],以获取对对称幺半理论分配律以及将弦图理论组合在一起的其他方式的更系统介绍。
3 作为图的弦图
上一节将弦图作为一种语法引入了。然而,这种形式化方法的一个优势在于,弦图也可以被当作带有节点和边的图来处理。这种视角通常便于研究弦图中与其组合结构(而非语法结构)相关的性质,例如两个组件之间是否存在路径。探索弦图组合视角的另一个重要原因在于,它们的图表示“吸收”了(2.3)中展示的对称幺半范畴定律。因此,对于某些计算任务(如重写,见第6.1节),它比语法表示更为适应。本节的目标是说明如何将弦图形式化地解释为图。
作为起点,让我们以之前考虑过的一个弦图为例:
![]()
如果我们抛开支撑这种表示的项结构,尝试将其理解为一种类似图的结构,看似最自然的方法是将盒子视为图的节点,将连线视为图的边。事实上,这通常是弦图作为数学记号在早期所采用的预期解释;例如参见[77]。这种方法面临的一个直接挑战是,“普通”的图并不够用:弦图呈现出松散的、开放式的边,它们只在一侧甚至没有一侧连接到节点,例如,“恒等”连线的图形表示:x。
历史上,解决这个问题的方法是将一种更复杂的图概念作为解释,这种图配备了一种拓扑结构,从中可以定义边何时是“松散的”、“半松散的”、“固定的”等等;参见[77]。另一种较新的方法将弦图理解为具有两种节点的图,其中第二种节点仅仅扮演一种官僚角色,即为那些本来会被画成松散的边提供一个端点[46]。
我们提出的方法遵循[13]。我们不把盒子视为节点,而是视为超边:即连接节点列表(而不是单个节点)的边。这种视角允许我们使用一种众所周知的数据结构(比上述结构更简单),称为超图:超图中唯一出现的实体是超边和节点:它们分别解释弦图中的盒子和连线的松散端。那么连线本身呢?它们仅仅是对超边如何与相关节点连接的描绘。这种解释适用于我们的主要例子如下:
![]()
![]()
为了将这种映射转变为一种形式化的解释,我们需要理解如何处理弦图的组合。直观上,并行组合很简单:如果我们将一个超图叠放在另一个超图之上,我们仍然得到一个有效的超图。例如:
![]()
为了将这种映射转变为一种形式化的解释,我们需要理解如何处理弦图的组合。直观上,并行组合很简单:如果我们将一个超图叠放在另一个超图之上,我们仍然得到一个有效的超图。例如:
![]()
![]()
![]()
得益于这一附加信息,开超图自带了一种内置的顺序组合概念,模仿弦图的顺序组合。只要第一个开超图的右接口与第二个开超图的左接口重合,我们就可以将这两个开超图进行顺序组合。
![]()
![]()
换言之,垂直组合取各接口和超图的不交并,而水平组合则识别中间接口的标签,并将它们作为节点纳入复合超图中。
![]()
![]()
![]()
![]()
这些例子有一个共同点:节点被允许比在(3.1)解释的像中表现得更加自由。例如,在第一个超图中,有一个“内部”节点(不在接口上)具有多条指向超边的出向连接。在第二个超图中,有一个没有任何入向连接的内部节点。最后,第三个超图具有一个可以在左接口上被插入两次的节点;当在左侧与另一个超图组合时,它将有两条入向连接。
![]()
![]()
此外,任何对应于弦图的超图都是无环的:不存在包含同一节点两次的有向路径。这两个性质足以刻画弦图。
![]()
定理3.3解决了何种开超图对应于“语法生成”的弦图这一问题。我们也可以问反过来的问题:我们需要在弦图的代数规范中添加什么,才能捕捉所有的开超图?
值得注意的是,例2.18中的特殊且交换的Frobenius幺半群正好适合这个角色。事实上,我们可以将例2.18中的运算解释为离散开超图:
![]()
直观地说,Frobenius生成元建模了一个节点具有多条或没有入向/出向连接的可能性,正如上述例子中那样。如果我们现在考虑在上增加了Frobenius幺半群生成运算的弦图,我们就可以推断出前述开超图对应的弦图:
![]()
![]()
4 弦图的范畴
操作弦图对初学者来说可能会令人困惑,因为实际上存在许多不同的变体,每一种都授权或禁止不同的形变和操作。更糟的是,许多论文会假定读者熟悉作者特定变体的游戏规则,并掩盖基本的变换。这未必是件坏事,因为弦图的目的是作为一种有用的计算工具,一种通过将无关细节吸收到记号本身的拓扑结构中,从而赋能其使用者的语法。本节旨在传达读者在文献中最可能遇到的最常见形式的基本规则。我们将深入探讨在每种语境下被授权和被禁止的操作,并通过几个例子加以说明。
在前面的章节中,我们有意选择从对称幺半范畴的弦图开始。让我们简要回顾一下游戏规则:我们被允许水平地组合盒子,只要连线的类型匹配,并且可以不受限制地垂直组合。此外,我们被允许以任何我们想要的方式交叉连线,并且多个连线交叉的任意垂直或水平复合的唯一相关结构,就是它所定义的连线的结果排列。
我们现在将看到,存在各种方式来加强或削弱这些规则以及所考虑的弦图类别。对于愿意进一步深入这一主题的读者,我们推荐Selinger关于幺半范畴图解语言的广泛综述[106]。
原文链接:https://www.cambridge.org/core/books/an-introduction-to-string-diagrams-for-computer-scientists/3CDAF8F57D2299F0EACA3354E9757CFD
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.