文字列図

ストリング ダイアグラムは、モノイド カテゴリ内の射、またはより一般的には2 カテゴリ内の 2 セルを表すための正式なグラフィカル言語です。ストリング ダイアグラムは、応用カテゴリ理論の主要なツールです。ベクトル空間のモノイド カテゴリとテンソル積を持つ線型マップで解釈される場合、テンソル ネットワークまたはペンローズ グラフィカル表記法と呼ばれます。これにより、量子理論の公理がモノイド カテゴリの言語で表現されるカテゴリカル量子力学が開発されました。

ギュンター・ホッツは電子回路を形式化するために弦図の最初の数学的定義を与えた。^[1]しかし、弦図の発明は通常ロジャー・ペンローズの功績とされ、^[2]ファインマン図もその先駆けとされている。^{[3]これらは後に}アンドレ・ジョヤルとロス・ストリートの独創的な論文で自由モノイド圏の矢印として特徴付けられた。^[4]これらの最初の論文の図は手描きであったが、LaTeXやPGF/TikZなどの組版ソフトウェアの出現により、弦図の出版はより広まった。^[5]

チャールズ・サンダース・パースの存在グラフと図式的推論は、おそらくストリング・ダイアグラムの最古の形式であり、有限集合のモノイド圏と直積との関係で解釈される。^{[6]パースの存在グラフ}の同一性線はフロベニウス代数として公理化でき、カットはホムセット上の単項演算子であり、論理否定を公理化する。これにより、ストリング・ダイアグラムは、ゴットロープ・フレーゲの「意味論」の一次元構文とは独立に発明された、一階述語論理のための健全で完全な二次元演繹システムとなる。 ^[7]

ストリング ダイアグラムは、プロセスを表すボックス と、ボックスによって処理される入力システムと出力システムを表す上部と下部から入ってくるワイヤのリストで構成されています。署名と呼ばれるワイヤとボックスのコレクションから始めて、帰納法によってすべてのストリング ダイアグラムのセットを生成できます。 ${\displaystyle f:x\to y}$ ${\displaystyle x}$${\displaystyle y}$${\displaystyle f}$

• 各ボックスは文字列ダイアグラムです。${\displaystyle f:x\to y}$
• 各ワイヤのリストについて、そのアイデンティティは入力システムに何もしないプロセスを表す文字列図であり、平行なワイヤの束として描かれます。${\displaystyle x}$ ${\displaystyle {\text{id}}(x):x\to x}$
• ストリング図との各ペアについて、そのテンソルはプロセスの並列合成を表すストリング図であり、2つの図の水平連結として描かれます。${\displaystyle f:x\to y}$${\displaystyle f':x'\to y'}$ ${\displaystyle f\otimes f':xx'\to yy'}$
• ストリング ダイアグラムとの各ペアについて、それらの合成はプロセスの順次合成を表すストリング ダイアグラムであり、2 つのダイアグラムの垂直連結として描画されます。${\displaystyle f:x\to y}$${\displaystyle g:y\to z}$ ${\displaystyle g\circ f:x\to z}$

クリーネの星が 自由モノイド、つまり集合 内の要素を持つリストの集合を表すものとします。 ${\displaystyle X^{\star}}$${\displaystyle X}$

モノイド署名は 次のように与えられます。 ${\displaystyle \Sigma }$

• 生成オブジェクトの集合。生成オブジェクトのリストは型とも呼ばれる。${\displaystyle \Sigma _{0}}$${\textstyle \Sigma _{0}^{\star }}$
• 生成矢印のセット（ボックスとも呼ばれる）${\displaystyle \Sigma _{1}}$
• 各ボックスにドメインとコドメイン、つまり入力タイプと出力タイプを割り当てる関数のペア。${\displaystyle {\text{dom}},{\text{cod}}:\Sigma _{1}\to \Sigma _{0}^{\star }}$

モノイド署名の射は、定義域および余定義域と互換性のある関数と関数のペア、つまり、およびとなるものです。こうして、モノイド署名とその射の カテゴリが得られます。${\displaystyle F:\Sigma \to \Sigma '}$${\displaystyle F_{0}:\Sigma _{0}\to \Sigma '_{0}}$${\displaystyle F_{1}:\Sigma _{1}\to \Sigma '_{1}}$${\displaystyle {\text{dom}}\circ F_{1}\ =\ F_{0}\circ {\text{dom}}}$${\displaystyle {\text{cod}}\circ F_{1}\ =\ F_{0}\circ {\text{cod}}}$${\displaystyle \mathbf {MonSig} }$

モノイドカテゴリをその基底シグネチャに送り、モノイド関数をその基底シグネチャの射に送る忘却 関数があります。つまり、恒等写像、合成、テンソルを忘れます。自由関数、つまり忘却関数の左随伴関数は、モノイドシグネチャをそれが生成する自由モノイドカテゴリに送ります。 ${\displaystyle U:\mathbf {MonCat} \to \mathbf {MonSig} }$ ${\displaystyle C_{-}:\mathbf {MonSig} \to \mathbf {MonCat} }$${\displaystyle \Sigma }$ ${\displaystyle C_{\Sigma}}$

弦図（から生成子を持つ）は、自由モノイド圏 の矢印です。^[8]モノイド圏 の解釈は、モノイド関手 によって定義され、自由性によりモノイド署名 の射によって一意に決定されます。直感的には、生成オブジェクトと矢印のイメージが与えられたら、それらが生成するすべての図のイメージは固定されます。 ${\displaystyle \Sigma }$${\displaystyle C_{\Sigma}}$${\displaystyle D}$${\displaystyle F:C_{\Sigma }\to D}$${\displaystyle F:\Sigma \to U(D)}$

位相グラフは、1 次元セル複合体とも呼ばれ、ハウスドルフ空間、ノードの閉じた離散サブセット、およびエッジと呼ばれる連結コンポーネントの集合の組です。各エッジは、 および の境界を持つ開区間に同相で、 となります。 ${\displaystyle (\Gamma ,\Gamma _{0},\Gamma _{1})}$ ${\displaystyle \ガンマ}$ ${\displaystyle \Gamma _{0}\subseteq \Gamma }$ ${\displaystyle \Gamma _{1}}$${\displaystyle \Gamma_{0}}$${\textstyle \Gamma -\Gamma _{0}=\coprod \Gamma _{1}}$

の2 つの実数間の平面グラフは、 に埋め込まれた有限位相グラフであり、すべての点はノードでもあり、 の 1 つのエッジの閉包に属します。このような点は外部ノードと呼ばれ、ストリング ダイアグラムのドメインとコドメイン、つまり上部境界と下部境界に接続されたエッジのリストを定義します。その他のノードは内部ノードと呼ばれます。 ${\displaystyle a,b\in \mathbb {R} }$${\displaystyle a<b}$${\displaystyle \mathbb {R} \times [a,b]}$${\displaystyle x\in \Gamma \ \cap \ \mathbb {R} \times \{a,b\}}$${\displaystyle x\in \Gamma _{0}}$${\displaystyle \Gamma _{1}}$${\displaystyle {\text{dom}}(\Gamma ),{\text{cod}}(\Gamma )\in \Gamma _{1}^{\star }}$${\displaystyle f\in \Gamma _{0}\ -\ \{a,b\}\times \mathbb {R} }$

平面グラフは、垂直投影がすべてのエッジに対して単射である場合に、プログレッシブ（横臥グラフとも呼ばれます）です。直感的には、プログレッシブ平面グラフのエッジは、後方に曲がることなく上から下に進みます。その場合、指定されたノードをソースとターゲットとして、各エッジに上から下への方向を与えることができます。次に、ソースとターゲットを持つエッジのリストによって指定された各内部ノードのドメインとコドメインを定義できます。 ${\displaystyle e\to [a,b]}$${\displaystyle e\in \Gamma _{1}}$${\displaystyle {\text{dom}}(f),{\text{cod}}(f)\in \Gamma _{1}^{\star }}$${\displaystyle f}$

平面グラフは、垂直投影が単射である場合、つまり 2 つの内部ノードが同じ高さにない場合に汎用的です。その場合、上から下に順序付けられた内部ノードの リストを定義できます。${\displaystyle \Gamma _{0}-\{a,b\}\times \mathbb {R} \to [a,b]}$${\displaystyle {\text{boxes}}(\Gamma )\in \Gamma _{0}^{\star }}$

プログレッシブ平面グラフは、ドメインとコドメインと互換性のある方法で 、エッジから生成オブジェクトへの関数と内部ノードから生成矢印への関数のペアを備えている場合、モノイド署名によってラベル付けされます。${\displaystyle \Sigma }$${\displaystyle v_{0}:\Gamma _{1}\to \Sigma _{0}}$${\displaystyle v_{1}:\Gamma _{0}-\{a,b\}\times \mathbb {R} \to \Sigma _{1}}$

平面グラフの変形は連続写像 であり、 ${\displaystyle h:\Gamma \times [0,1]\to [a,b]\times \mathbb {R} }$

• の像はすべての に対して平面グラフを定義します。${\displaystyle h(-,t)}$${\displaystyle t\in [0,1]}$
• すべて に対して、がいくつか に対して内部ノードである場合、それはすべて に対して内部です。${\displaystyle x\in \Gamma _{0}}$${\displaystyle h(x,t)}$${\displaystyle t}$${\displaystyle t\in [0,1]}$

変形が累進的（一般、ラベル付き）であるとは、すべての に対して が累進的（一般、ラベル付き）である場合を指します。変形が との同値関係を誘導するのは、および を満たすが存在する場合のみです。ストリング ダイアグラムは、ラベル付き累進平面グラフの同値類です。実際、次のように定義できます。 ${\displaystyle h(-,t)}$${\displaystyle t\in [0,1]}$${\displaystyle \Gamma \sim \Gamma '}$${\displaystyle h}$${\displaystyle h(-,0)=\ガンマ }$${\displaystyle h(-,1)=\ガンマ '}$

• 何らかのタイプでラベル付けされた平行辺の集合としての恒等図、${\displaystyle {\text{id}}(x)}$${\displaystyle x\in \Sigma _{0}^{\star }}$
• 2つの図を垂直に連結したもので、最初の図の余領域が2番目の図の領域と同一視される。
• 2 つの図のテンソルを水平方向の連結として表します。

幾何学的定義は圏論と低次元位相の間のつながりを明示的にしますが、文字列図をコンピュータ代数システムで形式化し、計算問題の定義に使用するには、組み合わせ論的定義が必要です。そのような定義の1つは、署名、恒等式、合成、テンソルによって生成される適切に型付けされた式の同値類として文字列図を定義することです。実際には、文字列図を、上で定義したラベル付きジェネリックプログレッシブ平面グラフと一対一であるジェネリック形式の式としてエンコードする方が便利です。

モノイド署名 を修正します。レイヤーは、左側の型、中央のボックス、右側の型の3 つ組として定義されます。レイヤーには、明らかな方法で定義されたドメインとコドメインがあります。これにより、型を頂点、レイヤーを辺とする有向マルチグラフ(矢印とも呼ばれます) が形成されます。文字列ダイアグラムは、このマルチグラフのパスとしてエンコードされます。つまり、次のように表されます。 ${\displaystyle \Sigma }$${\displaystyle (x,f,y)\in \Sigma _{0}^{\star }\times \Sigma _{1}\times \Sigma _{0}^{\star }=:L(\Sigma )}$${\displaystyle x}$${\displaystyle f}$${\displaystyle y}$${\displaystyle {\text{dom}},{\text{cod}}:L(\Sigma )\to \Sigma _{0}^{\star }}$${\displaystyle d}$

• 出発点としてのドメイン${\displaystyle {\text{dom}}(d)\in \Sigma _{0}^{\star }}$
• 長さ、${\displaystyle {\text{len}}(d)=n\geq 0}$
• リスト${\displaystyle {\text{layers}}(d)=d_{1}\dots d_{n}\in L(\Sigma )}$

となり、すべての に対して成り立ちます。実際、レイヤーの明示的なリストは冗長であり、各レイヤーの左側の型の長さ (オフセット と呼ばれる) を指定すれば十分です。型によるダイアグラムのウィスカーは、各レイヤーの右側への連結として定義され、左側のウィスカーに対しては対称的です。次に、次のように定義できます。 ${\displaystyle {\text{dom}}(d_{1})={\text{dom}}(d)}$${\displaystyle {\text{cod}}(d_{i})={\text{dom}}(d_{i+1})}$${\displaystyle i<n}$ ${\displaystyle d\otimes z}$${\displaystyle d=(x_{1},f_{1},y_{1})\dots (x_{n},f_{n},y_{n})}$${\displaystyle z}$${\displaystyle d\otimes z=(x_{1},f_{1},y_{1}z)\dots (x_{n},f_{n},y_{n}z)}$${\displaystyle z\otimes d}$

• およびとの恒等図、${\displaystyle {\text{id}}(x)}$${\displaystyle {\text{len}}({\text{id}}(x))=0}$${\displaystyle {\text{dom}}({\text{id}}(x))=x}$
• 2つの図をレイヤーのリストの連結として構成する。
• ウィスカーリングの合成としての2つの図のテンソル。${\displaystyle d\otimes d'=d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'}$

図は一般的な形式（つまり、各レイヤーに 1 つのボックスが含まれている）であるため、テンソルの定義は必然的に偏っていることに注意してください。左側の図は右側の図よりも上になります。反対の定義を選択することもできます。 ${\textstyle d\otimes d'={\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$

2 つの図は、インターチェンジャーによって生成された合同関係の同じ同値類にあるときはいつでも、(モノイド カテゴリの公理まで) 等しいです。つまり、2 つの連続するレイヤーのボックスが接続されていない場合は、それらの順序を入れ替えることができます。直感的には、2 つの並列プロセス間に通信がない場合、それらの発生順序は無関係です。 $${\displaystyle d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'\quad =\quad {\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$$

自由モノイド圏の単語問題、すなわち与えられた2つの図が等しいかどうかを決定する問題は、多項式時間で解くことができる。インターチェンジャーは、境界連結図のサブセット上の合流型 書き換えシステムであり、つまり平面グラフにドメインやコドメインに接続されていない連結成分が1つしかなく、エックマン-ヒルトンの議論が適用されない場合である。^[9]

この考え方は、ポアンカレ双対性を用いて次元dの構造を次元2-dの構造で表現するというものである。したがって、

• 物体は平面の一部によって表され、
• 1セルは、平面を2つに分ける垂直線（ストリングと呼ばれる）によって表される（右側がAに対応し、左側がBに対応する）。${\displaystyle f:A\to B}$
• 2 セルは、文字列の交差 (リンクの上のfに対応する文字列、リンクの下のgに対応する文字列) によって表されます。${\displaystyle \alpha :f\Rightarrow g:A\to B}$

2 つのセルの並列構成は図の水平方向の並置に対応し、順次構成は図の垂直方向の並置に対応します。

モノイド カテゴリは、単一の 0 セルを持つ 2 カテゴリと同等です。直感的に、モノイド カテゴリから 2 カテゴリに移行することは、文字列図の背景に色を追加することに相当します。

2 つのカテゴリとの間の随伴 を考えます。ここで はの左随伴であり、自然変換と はそれぞれ単位と余単位です。これらの自然変換に対応するストリング ダイアグラムは次のとおりです。 ${\displaystyle (F,G,\eta ,\varepsilon )}$${\displaystyle {\mathcal {C}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle F:{\mathcal {C}}\leftarrow {\mathcal {D}}}$${\displaystyle G:{\mathcal {C}}\rightarrow {\mathcal {D}}}$ ${\displaystyle \eta :I\rightarrow GF}$${\displaystyle \varepsilon :FG\rightarrow I}$

恒等関数に対応する文字列は点線で描画され、省略できます。 付加関数の定義には、次の等式が必要です。

${\displaystyle {\begin{aligned}(\varepsilon F)\circ F(\eta )&=1_{F}\\G(\varepsilon )\circ (\eta G)&=1_{G}\end{aligned}}}$

最初のものは次のように描かれている

すべてのオブジェクトが左と右の随伴を持つモノイド カテゴリは、剛性カテゴリと呼ばれます。剛性カテゴリのストリング ダイアグラムは、非進行平面グラフとして定義できます。つまり、エッジは後方に曲がることができます。

カテゴリー量子力学の文脈では、これはスネーク方程式として知られています。

ヒルベルト空間 のカテゴリは固定されており、この事実は量子テレポーテーションプロトコルの正しさの証明の基礎となっています。付加の単位と余単位は、それぞれベル状態とベル測定の抽象化です。アリスとボブがエンタングルド状態の 2 つの量子ビットY と Z を共有し、アリスが Y と別の量子ビット X の間で (後選択) エンタングルド測定を実行すると、この量子ビット X はアリスからボブにテレポートされます。量子テレポーテーションは恒等写像です。

図式的計算の図解:カテゴリカル量子力学でモデル化された量子テレポーテーションプロトコル。

同じ等式は、自然言語意味論における情報の流れの概念を捉える前群文法の定義にも現れています。この観察は、 DisCoCatフレームワークと量子自然言語処理の開発につながりました。

モノイド圏の矢印を追加構造で表現するために、ストリングダイアグラムの拡張が数多く導入され、セリンジャーのモノイド圏のグラフィカル言語の調査で分類されているグラフィカル言語の階層を形成している。 ^[10]

• 3 次元図による編組モノイド カテゴリ、編組群の一般化。
• 対称群の一般化であり、辺が交差できる 4 次元図を持つ対称モノイド カテゴリ。
• エッジが無向な 3 次元図を持つリボン カテゴリ。結び目図の一般化です。
• ペンローズのグラフィカル表記法の一般化であり、辺が無向な 4 次元図を持つコンパクトな閉カテゴリです。
• すべての図が水平方向に反射するダガー カテゴリ。

ストリング ダイアグラムは、次の研究対象を形式化するために使用されてきました。

• 並行性理論^[11]
• 人工ニューラルネットワーク^[12]
• ゲーム理論^[13]
• ベイズ確率^[14]
• 意識^[15]
• マルコフカーネル^[16]
• シグナルフローグラフ^[17]
• 接続詞的質問^[18]
• 双方向変換^[19]
• カテゴリカル量子力学
• 量子回路、測定ベースの量子コンピューティング、量子エラー訂正については、ZX計算を参照
• 自然言語処理については、DisCoCat を参照してください。
• 量子自然言語処理

• 証明ネット、線型論理における証明を表すために使用される文字列図の一般化
• 存在グラフ、第一階述語論理の式を表すために使用される文字列図の前身
• ペンローズのグラフィカル記法とファインマン図、物理学における弦図の2つの先駆者
• テンソルネットワーク、ベクトル空間におけるストリング図の解釈、線形写像、テンソル積

• TheCatsters (2007). ストリングダイアグラム 1 (ストリーミングビデオ) . Youtube. 2021-12-19 にオリジナルからアーカイブされました。
• nラボのストリング ダイアグラム
• DisCoPy、文字列図を計算するための Python ツールキット

• ウィキメディア・コモンズのストリング・ダイアグラムに関連するメディア