このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

型付き半グラフと指標

テンソルの可視化のための半グラフ」において、半グラフの定義をひとつに決めました。素の半グラフ〈plain semi-graph〉だけでなくて、様々な構造を追加した半グラフ〈structured semi-graph〉も必要になります。

ここでは、ポートに(必然的にワイヤーにも)型が付いた型付き半グラフ〈typed semi-graph〉を考えます。また、ボックスの型の仕様である指標〈signature〉も定義します。データベースへの応用を念頭に置いていますが、型付き半グラフとその指標は他の目的でも使えるでしょう。$`\newcommand{\mrm}[1]{\mathrm{#1}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\twoto}{\Rightarrow }
\newcommand{\In}{\text{ in } }
%\newcommand{\Imp}{ \Rightarrow }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\hyp}{\text{-} }
%\newcommand{\op}{\mathrm{op} }
\newcommand{\id}{\mathrm{id} }
\newcommand{\B}{\partial } % boundary
\newcommand{\mbf}[1]{\mathbf{#1}}
\newcommand{\pto}{ \supseteq\!\to }
\require{color} % 緑色
\newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }%
\newcommand{\For}{\Keyword{For } }%
\newcommand{\Define}{\Keyword{Define } }%
\newcommand{\Subject}{\Keyword{Subject } }%
\newcommand{\Where}{\Keyword{Where } }
%\newcommand{\Let}{\Keyword{Let } }
`$

内容:

半グラフ

半グラフの定義と基本概念は「テンソルの可視化のための半グラフ」を見てください。有限な無サークル半グラフを単に半グラフ〈semi-graph〉と呼びます。

$`A`$ が半グラフのとき、その構成素を次のように表します。

  • $`\mrm{Port}(A)`$ : $`A`$ のポートの集合
  • $`\mrm{Box}(A)`$ : $`A`$ のボックスの集合
  • $`\mrm{canvas}_A`$ : $`A`$ のキャンバスボックスをポインティングする写像
  • $`\mrm{belong}_A`$ : $`A`$ の所属写像
  • $`\mrm{wire}_A`$ : $`A`$ のワイヤリング対合
  • $`\mrm{Wire}(A)`$ : $`A`$ のワイヤーの集合

図式で描くと次のようになります。$`\pi`$ は商集合への標準的射影です。

$`\quad \xymatrix{
{} & {\bf 1} \ar[d]^{\mrm{canvas}_A}
\\
% @(inDir, outDir)
*{\mrm{Port}(A)} \ar@(ul, dl)[0,0]_{\mrm{wire}_A}
\ar[r]^-{\mrm{belong}_A}
\ar[d]^{\pi}
& \mrm{Box}(A)
\\
{\mrm{Wire}_A}
& {}
}\\
\quad \text{ in } {\bf FinSet}
`$

ワイヤーの集合は定義に含める必要はありません。ポインティング写像を要素と同一視して、$`\mrm{canvas}_A \in \mrm{Box}(A)`$ とも書きます。

$`A`$ と $`B`$ が半グラフのとき、2つの写像を考えます。

$`\quad \varphi_\mrm{port} : \mrm{Port}(A) \to \mrm{Port}(B) \In {\bf Set}\\
\quad \varphi_\mrm{box} : \mrm{Box}(A) \to \mrm{Box}(B) \In {\bf Set}
`$

これらが半グラフの構造を保つとき、$`\varphi = (\varphi_\mrm{port}, \varphi_\mrm{box})`$ は半グラフのあいだの準同型射〈homomorphism〉であると言います。より詳しく言えば、以下の図式がすべて可換になることです。

$`\require{AMScd}
\quad \begin{CD}
\mrm{Port}(A) @>{\varphi_\mrm{port}}>> \mrm{Port}(B)\\
@V{\mrm{belong}_A}VV @VV{\mrm{belong}_B}V \\
\mrm{Box}(A) @>{\varphi_\mrm{box}}>> \mrm{Box}(B)
\end{CD}
`$

$`\quad \begin{CD}
{\bf 1} @= {\bf 1}\\
@V{\mrm{canvas}_A}VV @VV{\mrm{canvas}_B}V \\
\mrm{Box}(A) @>{\varphi_\mrm{box}}>> \mrm{Box}(B)
\end{CD}
`$

$`\quad \begin{CD}
\mrm{Port}(A) @>{\varphi_\mrm{port}}>> \mrm{Port}(B)\\
@V{\mrm{wire}_A}VV @VV{\mrm{wire}_B}V \\
\mrm{Port}(A) @>{\varphi_\mrm{port}}>> \mrm{Port}(B)
\end{CD}
`$

半グラフを対象として、半グラフのあいだの準同型射を射とする圏を構成できます。この圏を半グラフの圏〈category of semi-graphs〉と呼び $`{\bf SemiGraph}`$ と書きます。

半グラフ $`A`$ の内部ボックス〈inner box〉の集合を次のように定義します。

$`\quad \mrm{IBox}(A) := \mrm{Box}(A)\setminus \{\mrm{canvas}_A \}`$

キャンバスボックスだけを含む単元集合は:

$`\quad \mrm{OBox}(A) := \{\mrm{canvas}_A \}`$

当然ながら、

$`\quad \mrm{Box}(A) = \mrm{IBox}(A) + \mrm{OBox}(A)`$

ポートも、内部ポート〈inner port〉と外部ポート〈outer port〉に区分できます。

$`\quad \mrm{IPort}(A) := {\mrm{belong}_A}^{-1}(\mrm{IBox}(A) )\\
\quad \mrm{OPort}(A) := {\mrm{belong}_A}^{-1}(\mrm{OBox}(A) )\\
\:\\
\quad \mrm{Port}(A) = \mrm{IPort}(A) + \mrm{OPort}(A)
`$

ここでの $`\mrm{I/O}`$ は Input/Output ではなくて Inner/Outer ですから注意してください。Input/Output は、ポート極性とワイヤーの向き付けで定義するのでまったく別な話です(「テンソルの可視化のための半グラフ」参照)。しかも、Input/Output は時間方向/因果方向/データフローなどとはまったく無関係かも知れないのです。言葉からの安易な連想はやめましょう*1

ちなみに、次の四角形図式はプルバック四角形〈ファイバー積四角形〉になります。

$`\quad\begin{CD}
\mrm{OPort}(A) @>{!}>> {\bf 1} \\
@V{\subseteq}VV @VV{\mrm{canvas}_A}V \\
\mrm{Port}(A) @>{\mrm{belong}_A }>> \mrm{Box}(A)
\end{CD}
`$

用語に関する注意

ほとんど常に言葉〈用語〉は錯綜するものなので、慣れている人は平気でしょうが、老婆心から念のために注意しておきます。

テンソルの可視化のための半グラフ」で述べたように、以下の横方向は同義語です。

半辺 ポート
頂点 ボックス
ワイヤー
境界写像 所属写像
パートナー指定対合 ワイヤリング対合
未定義値〈ボトム〉 キャンバスボックス

構成素の呼び名を変えても、組み合わせ構造〈combinatorial structure〉とそれに関する議論は何も変わりません。が、描画法とメンタルモデルは変わります。

素の半グラフ $`(P, B, c, b, w)`$ は、ワイヤーの向きも(ひとつのボックスに所属する)ポート間の順序もありません。次の写像が追加されれば、極性付き半グラフ〈polarized semi-graph〉になります。

$`\quad p: P \to \{+, -\}`$

極性付け〈polarization〉 $`p`$ が適切な条件を満たすなら、すべてのワイヤーに向き〈direction〉が付きます。このとき極性付き半グラフは有向半グラフ〈directed semi-graph〉になります。

以下の横方向は同義語です。

半グラフ 無向ストリング図 無向ネットワーク
極性付き半グラフ
有向半グラフ ストリング図 有向ネットワーク

ちなみに、極性〈polarity〉の同義語には次があります。

  • 符号〈sign〉
  • 偶奇性〈parity〉
  • 電荷〈charge〉

したがって、「符号付き半グラフ」は「極性付き半グラフ」の同義語になります。幾つかの同義語があると、複合語の同義語の個数は組み合わせ爆発を起こすので(「用語のバリエーション記述のための正規表現」参照)、イチイチ列挙はしません。

半グラフの直和

前々節で、圏 $`{\bf SemiGraph}`$ を定義しました。ことのついでに、この圏に対称モノイド構造を入れましょう。まず、モノイド単位になる半グラフ $`\mrm{O}`$ を定義します。$`\mrm{O}`$ は次のように定義します。

$`\quad \mrm{Port}(\mrm{O}) := \emptyset\\
\quad \mrm{Box}(\mrm{O}) := {\bf 1}
`$

残りの構成素 $`\mrm{canvas}, \mrm{belong}, \mrm{wire}`$ は自動的に決まってしまいます。

$`\quad \xymatrix{
{} & {\bf 1} \ar[d]^{\mrm{canvas}_\mrm{O}}
\\
% @(inDir, outDir)
*{\emptyset} \ar@(ul, dl)[0,0]_{\mrm{wire}_\mrm{O}}
\ar[r]^-{\mrm{belong}_\mrm{O}}
& {\bf 1}
}\\
\quad \text{ in } {\bf FinSet}
`$

$`A, B \in |{\bf SemiGraph}|`$ とします。対象 $`A`$ と $`B`$ の直和を定義しましょう。それぞれのボックスの集合は、キャンバスボックスを基点として付点集合〈pointed set〉とみなせるので、付点集合の直和を作れます。それを、

$`\quad \mrm{Box}(A) \mathop{\dot{+}} \mrm{Box}(B)`$

と書きます。丁寧に書くと:

$`\quad \mrm{Box}(A) \mathop{\dot{+}} \mrm{Box}(B) := \\
\qquad (\mrm{Box}(A)\setminus \{\mrm{canvas}_A\}) + (\mrm{Box}(B)\setminus \{\mrm{canvas}_B\}) + \{\mrm{newcanvas} \}
`$

ここで、$`\mrm{newcanvas}`$ は新しく追加した要素で、新しく作った付点集合の基点になります。

もともとあった2個の基点(キャンバスボックス)を同一視して $`\mrm{newcanvas}`$ だと思うことにより次の写像が定義できます。

$`\quad m_{A, B} : \mrm{Box}(A) + \mrm{Box}(B) \to \mrm{Box}(A) \mathop{\dot{+}} \mrm{Box}(B)
`$

$`C := A + B`$ と置いて、半グラフ $`C`$ を以下のように定義します。$`\Subject`$で、定義すべきモノを宣言してから実際の定義を続けます。

$`\Subject C = A + B \in |{\bf SemiGraph}|\\
\Define \mrm{Port}(C) := \mrm{Port}(A) + \mrm{Port}(B)\\
\Define \mrm{Box}(C) := \mrm{Box}(A) \mathop{\dot{+}} \mrm{Box}(B)\\
\Define \mrm{canvas}_C := \mrm{newcanvas} \\
\Define \mrm{belong}_C := (\mrm{belong}_A + \mrm{belong}_B) ; m_{A, B}\\
\Define \mrm{wire}_C := (\mrm{wire}_A + \mrm{wire}_B)
`$

$`C = A + B`$ への入射〈injection〉は次のように定義します。

$`\Subject \iota^{A, B}_1 : A \to C = A + B \\
\Define (\iota^{A, B}_1)_\mrm{port} := \iota^{\mrm{Port}(A), \mrm{Port}(B)}_1\\
\Define (\iota^{A, B}_1)_\mrm{box} := \iota^{\mrm{Box}(A), \mrm{Box}(B)}_1 ; m_{A, B}
`$

第二入射 $`\iota^{A, B}_2`$ も同様に定義できます。$`\iota^{A, B}_i`$ が実際に半グラフの準同型射になること、直和と入射の条件(余デカルト性)を満たすことは確認する必要がありますが、その作業が済めば $`{\bf SemiGraph}`$ に対称なモノイド構造が載ります。次の対称モノイド圏(記号の乱用で書いてます)ができるわけです。

$`\quad {\bf SemiGraph} = ({\bf SemiGraph}, +, \mrm{O}, \alpha, \lambda, \rho, \sigma)`$

型付き半グラフ

$`T`$ を型の集合〈set of types〉だとします。型がなんであるかには言及しません。なんだっていいからです。$`T`$ は「型」と呼ばれる要素からなる集合に過ぎません。ただし、$`T`$ は空集合ではないとします。もっとも簡単な事例は $`T = {\bf 1}`$ です。$`T`$ は小さくない〈真に大きい〉集合でもかまいません*2。例えば $`T = |{\bf Set}|`$ 。

型をしばしば〈color〉とも呼びます。その呼び名のもとでは、$`T`$ は色の集合〈set of colors〉です。ここでは、(「色」ではなくて)「型」を使いますが、呼び名なんて(合意されていれば)なんだってかまいません

半グラフ $`(P, B, c, b, w)`$ の型付け〈typing〉とは、次の写像です。

$`\quad t: P \to T`$

次の図式が可換であることを要求します。

$`\quad \begin{CD}
P @>{t}>> T \\
@V{w}VV @| \\
P @>{t}>> T
\end{CD}
`$

つまり、ワイヤリング対合に関して型付けは不変です。すると、ワイヤリング対合から誘導された同値関係の同値類の上で同じ値を取るので、商集合 -- すなわちワイヤーの集合 $`W`$ に型付けを落とせます。次の図式を可換にする $`t'`$ が定義可能なわけです。

$`\quad \begin{CD}
P @>{t}>> T \\
@V{\pi}VV @| \\
W @>{t'}>> T
\end{CD}
`$

別な見方をすると、ワイヤーの集合 $`W`$ 上にあった型付け $`t'`$ を持ち上げると $`t`$ になります。

型付けを含めた構造 $`(P, B, c, b, w, t)`$ が型付き半グラフ〈typed semi-graph〉です。もちろん、色付き半グラフ〈colored semi-graph〉と呼んでもいいです。

$`A`$ が型付き半グラフのとき、追加の構成素である型付けは次のように表します。

  • $`\mrm{Type}(A)`$ : 型の集合 $`T`$
  • $`\mrm{type}_A`$ : 型付け写像 $`\mrm{Port}(A) \to \mrm{Type}(A)`$

ワイヤーの集合上の型付けは同じ名前をオーバロードします。

  • $`\mrm{type}_A`$ : ワイヤーの型付け写像 $`\mrm{Wire}(A) \to \mrm{Type}(A)`$

型の集合は型付き半グラフごとに決まるのではなくて、全体として $`T`$ に固定するとします。すると、型付き半グラフ $`A`$ は次の図式で書けます。

$`\quad \xymatrix{
T & {\bf 1} \ar[d]^{\mrm{canvas}_A}
\\
% @(inDir, outDir)
*{\mrm{Port}(A)} \ar@(ul, dl)[0,0]_{\mrm{wire}_A}
\ar[u]^{\mrm{type}_A}
\ar[r]^-{\mrm{belong}_A}
& \mrm{Box}(A)
}\\
\quad \text{ in } {\bf Set}
`$

$`T`$ が有限集合とは限らないので、$`\text{ in } {\bf Set}`$ と書いてますが、$`T`$ 以外の構成素は有限集合だと仮定しています。

$`A, B`$ が2つの$`T`$-型付き半グラフだとして、そのあいだの準同型射とは、半グラフのあいだの準同型射であり型付けも保存するものです。$`\varphi = (\varphi_\mrm{port}, \varphi_\mrm{box})`$ が型付けも保存するとは次の図式が可換になることです。

$`\quad \begin{CD}
\mrm{Port}(A) @>{\varphi_\mrm{port}}>> \mrm{Port}(B)\\
@V{\mrm{type}_A}VV @VV{\mrm{type}_B}V \\
T @= T
\end{CD}
`$

$`T`$-型付き半グラフを対象として、そのあいだの準同型射を射とする圏を構成できます。この圏を$`T`$-型付き半グラフの圏〈category of $`T`$-typed semi-graphs〉と呼び $`{\bf TypedSemiGraph}[T]`$ と書きます。

前節で定義した直和は$`T`$-型付き半グラフに対しても同様に定義できるので、$`{\bf TypedSemiGraph}[T]`$ を対称モノイド圏にできます。その対称モノイド圏を次のように書きます。

$`\quad {\bf TypedSemiGraph}[T] = ({\bf TypedSemiGraph}[T], + , \mrm{O}, \alpha, \lambda, \rho, \sigma)`$

$`{\bf TypedSemiGraph}[T]`$ から $`{\bf SemiGraph}`$ へは自明な忘却関手があります。

$`\quad \mathbb{U} : {\bf TypedSemiGraph}[T] \to {\bf SemiGraph} \In {\bf CAT}\\
\quad \mathbb{U} : {\bf TypedSemiGraph}[T] \to {\bf SemiGraph} \In {\bf SymMonCAT}
`$

次の圏同型(あるいは対称モノイド圏の同型)があります(圏同値より強い)。

$`\quad {\bf TypedSemiGraph}[{\bf 1}] \cong {\bf SemiGraph} \In {\bf CAT}\\
\quad {\bf TypedSemiGraph}[{\bf 1}] \cong {\bf SemiGraph} \In {\bf SymMonCAT}\\
`$

型付き半グラフの指標

型付き半グラフとその指標はしばしば混同されます。構造として似ているので無理もありません。が、その用途や意味は、型付き半グラフと指標ではだいぶ違います。

型付き半グラフの指標〈signature〉とは、型付き半グラフからキャンバスボックスとワイヤリング対合を取り除いた次の構造です。

$`\quad \xymatrix{
T & {}
\\
P
\ar[u]^{\mrm{type}}
\ar[r]^-{\mrm{belong}}
& B
}\\
\quad \text{ in } {\bf Set}
`$

$`S`$ が指標だとして、各構成素の呼び名・書き方は型付き半グラフと同じにします。すると、次のように書けます。

$`\quad \xymatrix{
T & {}
\\
*{\mrm{Port}(S)}
\ar[u]^{\mrm{type}_S}
\ar[r]^-{\mrm{belong}_S}
& *{\mrm{Box}(S)}
}\\
\quad \text{ in } {\bf Set}
`$

指標の場合、$`\mrm{Port}(S), \mrm{Box}(S)`$ に有限性の条件は課さないことにします。しかし、ボックスごとにポートが有限であるという条件(下)は課します。

$`\quad \forall b\in \mrm{Box}(S).\, {\mrm{belong}_S}^{-1}(b) \text{ is-finite-set}
`$

データベースの場合で言えば、$`\mrm{Box}(S)`$ がテーブル名の集合で、$`\mrm{Port}(S)`$ がすべてのテーブル名に渡るカラム名〈フィールド名〉の集合です。$`T`$ は(データベース用語での)“ドメイン”の集合です。$`\mrm{belong}_S`$ がカラム名がどのテーブル名のものであるかを指定します。$`\mrm{type}_S`$ は通常の意味のカラム名の型付け〈ドメイン付け〉を与えます。ここで出てくるテーブル名は、実際の個々のテーブルに付けられる固有名ではなくて、テーブルの類型的パターンに付けられるパターン名になります。

型付き半グラフの場合と同様に、$`\varphi = (\varphi_\mrm{port}, \varphi_\mrm{box})`$ が指標の準同型射〈homomorphism between signatures〉であることを定義できます。そして、指標を対象として指標のあいだの準同型射を射とする圏を構成できます。その圏を($`T`$-型付き半グラフの)指標の圏〈category of signatures for $`T`$-typeed semi-graphs〉と呼び $`{\bf TSGSign}[T]`$ と書きます。TSG は Typed Semi-Graph の短縮です。$`{\bf TSGSign}[T]`$ の要素をTSG指標〈TSG signature〉とも呼びます。

圏 $`{\bf TSGSign}[T]`$ にもモノイド構造(直和)を載せることができます。モノイド構造の作り方は圏 $`{\bf TypedSemiGraph}[T]`$ の場合と同様です。モノイド単位は以下の指標になります。

$`\quad \xymatrix{
T & {}
\\
\emptyset
\ar[u]
\ar[r]
& \emptyset
}\\
\quad \text{ in } {\bf Set}
`$

指標の記述構文(事例)

型の集合を $`T = \{ {\bf N}, {\bf String}, {\bf Year} \}`$ とします。$`T`$ の要素は集合で、それぞれ自然数の集合、文字列の集合、年の集合です。型の要素($`T`$ の要素の要素)は常識的な書き方をします。例えば、$`2023 \in {\bf Year}`$ 、この要素は $`2023\in {\bf N}`$ とは別物なので、$`\mrm{Y}2023`$ とか書いたほうがいいですが、文脈による区別も常識的にやるとします。

学生のテーブル、科目のテーブル、教員のテーブルを考えて、その仕様(テーブルスキーマ達)を以下のように記述します。プレーンテキストなので、型に太字は使ってません。

table 学生 : {
  番号: N,
  姓: String,
  名: String,
  学年: N
}

table 科目 : {
  番号: N,
  名: String,
  年: Year,
  担当: N
}

table 教員 : {
  番号: N,
  姓: String,
  名: String
}

table 受講 : {
  科目: N,
  学生: N
}

上記で記述される型付き半グラフの指標に $`\text{学校}`$ という固有名を付けます。指標 $`\text{学校}`$ を、前節の構成素達で記述してみます。構成素達とは:

  • $`\mrm{Port}(\text{学校})`$
  • $`\mrm{Box}(\text{学校})`$
  • $`\mrm{belong}_\text{学校}`$
  • $`\mrm{type}_\text{学校}`$

ポートの集合は、テーブル名とカラム名〈フィールド名〉をドットで繋いだ名前達とします。

$`\quad \mrm{Port}(\text{学校}) := \{\\
\qquad \text{学生.番号}, \text{学生.姓}, \text{学生.名},\text{学生.学年},\\
\qquad \text{科目.番号}, \text{科目.名}, \text{科目.年}, \text{科目.担当}, \\
\qquad \text{教員.番号}, \text{教員.姓}, \text{教員.名} , \\
\qquad \text{受講.科目}, \text{受講.学生}\\
\quad \}
`$

ボックスの集合はテーブル名の集合です。

$`\quad \mrm{Box}(\text{学校}) := \{ \text{学生}, \text{科目}, \text{教員}, \text{受講} \}`$

所属関数は明らかでしょう、一部だけ書き出します。

$`\quad \mrm{belong}_\text{学校} := (\\
\qquad \text{学生.番号} \mapsto \text{学生},\\
\qquad \text{学生.姓} \mapsto \text{学生}, \\
\qquad \text{学生.名} \mapsto \text{学生}, \\
\qquad \text{学生.学年} \mapsto \text{学生}, \\
\qquad \cdots\\
\qquad \text{受講.学生} \mapsto \text{受講} \\
\quad )`$

型付けも一部だけ書き出します。

$`\quad \mrm{type}_\text{学校} := (\\
\qquad \text{学生.番号} \mapsto {\bf N}\\
\qquad \text{学生.姓} \mapsto {\bf String}, \\
\qquad \text{学生.名} \mapsto {\bf String}, \\
\qquad \text{学生.学年} \mapsto {\bf N}, \\
\qquad \cdots\\
\qquad \text{受講.学生} \mapsto {\bf N} \\
\quad )`$

ここでは、あくまで組み合わせ構造(だけ)を記述しているので、「学生とはなんぞや」と問われても答えられません。自然言語〈日本語〉の語を使ったのは、それで連想される暗黙の(かつ曖昧な)意味が理解の助けになることを狙っています。が、あくまで暗黙で曖昧なので、そこに正式な意味論はありません。

型付き半グラフから作る指標

$`T`$ は固定した型の集合とします。$`S = (P, B, \mrm{belong}, \mrm{type}), S' = (P', B', \mrm{belong'}, \mrm{type'})`$ を2つのTSG指標〈型付き半グラフの指標〉とします。$`\varphi = (\varphi_\mrm{port}, \varphi_\mrm{box})`$ をTSG指標のあいだの射とします。つまり:

  • $`\varphi_\mrm{port} : P \to P' \In {\bf Set}`$
  • $`\varphi_\mrm{box} : B \to B' \In {\bf Set}`$
  • 以下の2つの図式は集合圏内で可換。

$`\quad \begin{CD}
P @>{\varphi_\mrm{port} }>> P' \\
@V{\mrm{belong}}VV @VV{\mrm{belong'}}V\\
B @>{\varphi_\mrm{box} }>> B'
\end{CD}
`$

$`\quad \begin{CD}
P @>{\varphi_\mrm{port} }>> P' \\
@V{\mrm{type}}VV @VV{\mrm{type'}}V\\
T @= T
\end{CD}
`$

TSG指標のあいだの射 $`\varphi`$ が局所同型〈locally isomorphic〉だとは次のことだとします; $`b\in B`$ に対して、$`b' := \varphi_\mrm{box}(b)`$ と置くと、次の写像が誘導されます。

$`\quad (\varphi_\mrm{port})_b : \mrm{belong}^{-1}(b) \to \mrm{belong'}^{-1}(b')`$

バンドルの言葉を使うなら、ファイバーのあいだの写像です。この写像が、すべての $`b\in B`$ に対して同型であるとき、$`\varphi`$ は局所同型です。

$`A`$ が型付き半グラフのとき、$`A`$ からTSG指標を作れます。例えば、次の図式のようなTSG指標が作れます。

$`\quad \begin{CD}
T \\
@A{ {\mrm{type}_A}|_{\mrm{IPort}(A)} }AA \\
\mrm{IPort}(A) @>{ {\mrm{belong}_A}|_{\mrm{IPort}(A)} }>> \mrm{IBox}(A)
\end{CD}
`$

ここで 縦棒は、写像の域の制限を表します。

これは、型付き半グラフの内部ポート/内部ボックスだけを取り出して、ワイヤリング対合を忘れたものです。こうして作ったTSG指標を、型付き半グラフの内部指標〈inner signature〉と呼び $`\mrm{Inner}(A)`$ と書くことにします。単に内部を取り出しただけではなくて、ワイヤリング対合がなくなっている(ポートの繋がりが切れている)ことに注意してください。

もうひとつ、次のような指標も作れます。

$`\quad \begin{CD}
T \\
@A{ {\mrm{type}_A}|_{\mrm{OPort}(A)} }AA \\
\mrm{OPort}(A) @>{ {\mrm{belong}_A}|_{\mrm{OPort}(A)} }>> \mrm{OBox}(A)
\end{CD}
`$

$`\mrm{OBox}(A) = \{\mrm{canvas}_A \}`$ なので、$`{\mrm{belong}_A}|_{\mrm{OPort}(A)}`$ は一意的に決まってしまう写像です。しかし、形を揃えるために上記の図式で表します。

これは、型付き半グラフの外部ポート/外部ボックス〈キャンバスボックス〉だけを取り出して、ワイヤリング対合を忘れたものです。こうして作ったTSG指標を、型付き半グラフの外部指標〈outer signature〉と呼び $`\mrm{Outer}(A)`$ と書くことにします。

$`\mrm{Inner}(A)`$ でも $`\mrm{Outer}(A)`$ でもワイヤー/ワイヤリングの情報が失われて、ボックスの仕様(付随しているポート達とその型達)だけが残っています。

型付き半グラフのプロファイル

さて、$`S`$ をTSG指標($`S \in {\bf TSGSign}[T]`$ として、型付き半グラフ $`A`$ ($`A \in |{\bf TypedSemiGraph}[T]|`$)の$`S`$-プロファイル写像〈$`S`$-profile map〉、または$`S`$-プロファイリング〈$`S`$-profiling〉とは、次のような射 $`\psi`$ です。

  • $`\psi : \mrm{Inner}(A) \to S \In {\bf TSGSign}[T]`$
  • $`\psi`$ は局所同型

型付き半グラフ $`(P, B, c, b, w, t)`$ に$`S`$-プロファイル写像 $`\psi`$ を加えた構造 $`(P, B, c, b, w, t, \psi)`$ を$`S`$-プロファイル付き$`T`$-型付き半グラフ〈$`S`$-profiled $`T`$-typed semi-graph〉と呼びます。

型付き半グラフ $`A`$ に$`S`$-プロファイルが付いているとはどういうことでしょうか? 指標 $`S`$ は、型付きボックス(付随しているポートに型が付いているボックス)のカタログだと考えられます。型付き半グラフ $`A`$ は、$`S`$ から幾つかの型付きボックスを(重複を許して)選んで、それらの型付きボックスをワイヤリングして作った半グラフになります。型付きボックスのカタログ $`S`$ からどの型付きボックスを選び取ったかを表現しているのがプロファイル写像 $`\psi`$ です。$`\psi_\mrm{box}(x) = b`$ ならば、半グラフ $`A`$ に出現しているボックス $`x`$ は、カタログ $`S`$ のボックス $`b`$ のコピーです。

型付き半グラフ $`A`$ が$`S`$-プロファイル付きだと言うことは、$`S`$ に列挙されている素材を使って $`A`$ を組み立てていることです。指標 $`S`$ (素材のカタログ)は固定して、その素材達から組み立てられた型付き半グラフ達の圏は次のように書きます。

$`\quad {\bf ProfTypedSemiGraph[T][S]}`$

この圏は:

  • 対象は、$`T`$ で型付け〈typing〉され、$`S`$ でプロファイリング〈profiling〉されたプロファイル付き型付き半グラフ
  • 射は、型付けとプロファイリングを保存する半グラフのあいだの準同型射

プロファイル付き型付き半グラフの圏〈category of profiled typed semi-graphs〉です。「プロファイル付き型付き」は長いし、型付きはプロファイル付きの前提なので、単にプロファイル付き半グラフの圏〈category of profiled semi-graphs〉とも呼びます。

今までと同様な手順で、プロファイル付き半グラフの圏にも対称モノイド構造を載せられます。対称モノイド構造〈直和〉が載ったプロファイル付き半グラフの圏は次のように書きます。

$`\quad {\bf ProfTypedSemiGraph[T][S]} = \\
\qquad ({\bf ProfTypedSemiGraph[T][S]}, +, \mrm{O}, \alpha, \lambda, \rho, \sigma)`$

おわりに

次の圏を構成しました。必要なら対称モノイド構造〈直和〉を使えます。

  1. $`{\bf SemiGraph}`$
  2. $`{\bf TypedSemiGraph}[T] \text{ where }T \in |{\bf Set}|`$ ($`T`$ は小さい集合のとき)
  3. $`{\bf TSGSign}[T] \text{ where }T \in |{\bf Set}|`$
  4. $`{\bf ProfTypedSemiGraph[T][S]} \text{ where }T \in |{\bf Set}|, S \in {\bf TSGSign}[T]`$

いずれの圏の対象も、組み合わせ構造〈combinatorial structure〉として定義されていますが、もともとは幾何的・位相的構造から抽出した組み合わせ構造なので(「テンソルの可視化のための半グラフ // 半グラフの幾何的・位相的な定義」参照)、対応した図形を描けます。つまり、視覚化と相性がいいのです。他の圏や計算系とも組み合わせて、色々な場面に適用・応用可能です。

*1:いくら注意しても、言葉からの連想で考える癖は抜けにくいようです。言霊恐ろしや。

*2:サイズの問題〈size issue〉が生じるので、小さくない集合は避けたほうが無難ですが。