「半グラフの二重圏と半グラフ変形」において、半グラフ変形をアルゴリズム的に捉えるために、基本変形を指令〈instruction〉と呼び、指令ニモニック（指令を表す記号）を組み合わせたある種のプログラムコードとして指令半グラフを導入しました。
指令や指令半グラフは、コンピュータの機械語や機械語プログラムのアナロジーです。つまり、半グラフと半グラフ変形の体系を定義することはコンピュータの機械語体系を設計することに似ています。とはいえ、現実のコンピュータを随分と抽象化しているし、実際の計算システムを載せる究極の土台のようなものが半グラフと半グラフ変形の体系です。そこで、抽象的原初的仮想的コンピュータをメタ計算系〈meta computing system〉と呼ぶことにします。
メタ計算系としての半グラフ＆半グラフ変形の体系では、データが半グラフです。コードも半グラフと指令ニモニックで表現できます。その意味で、このメタ計算系は（近似的に）同図像性〈homoiconicity〉を持ちます。計算〈メタ計算〉の基本となる指令を列挙します（「半グラフの二重圏と半グラフ変形」参照）。
- 架橋〈bridging〉： 2本の外部辺から1本の内部辺を作る
- 実縮減〈actual shrinking〉： 内部辺の両端を同一視して内部辺を消去
- 仮想縮減〈virtual shrinking〉： 2本の外部辺の2つの端点〈境界点〉を同一視して2本の外部辺を消去
- 頂点マージ〈vertex merging〉： 2個の頂点をまとめて1個の頂点にする。
内部辺を切り分ける切断〈cutting〉は指令に入れてません。
どの指令を使うかによって半グラフ変形を分類できます。
- 接合〈grafting〉： 架橋指令だけを使った半グラフ変形
- 縮約〈contraction〉： 縮減（実縮減と仮想縮減）だけを使った半グラフ変形
- マージャー〈merger〉： 頂点マージだけを使った半グラフ変形
一般のグラフ変形は、接合、縮約、マージャーをこの順で繋いで構成できます*1。
以上のような指令・変形を使って、既存の半グラフ変形の定義（末尾の参考文献リスト参照）を書き下したり、具体例をいじったりしてみたのですが、次のことに気付きました。
- 接合とその他の変形は別に扱ったほうが良さそう。
- 仮想縮減は要らない。
- 実縮減を、ループ辺への適用と非ループ辺への適用で分けたほうが良い。
半グラフに対する基本操作を次の3グループに分けるのが適切な気がします。
- 半グラフの直和〈direct sum〉
- 様々なタイプの接合
- その他の基本操作（ループ辺縮減〈loop edge shrinking〉、非ループ辺縮減〈non-loop edge shrinking〉、頂点マージ）
接合は、架橋を“繰り返し行う”というよりは、「半グラフに関わる諸概念 // マッチャー」で述べたマッチャー〈matcher〉によりインデックス〈パラメトライズ〉される演算の族と考えたほうが便利です。
半グラフのメタ計算系を項書き換え系〈term rewriting system〉とみなした場合、項は半グラフで、その他の基本操作が項の還元〈reduction〉になります。それ以上は還元できない項に相当するのはカローラです。書き換え〈計算〉の順次実行と並列実行〈同時実行〉の区別もあります。停止性や合流性は成立していそうです。項のアルファ変換〈alpha conversion〉も半グラフの亜群で実現できます。
半グラフのメタ計算系は原初的な計算系なので、その上に、より具体的・応用的なオブジェクトレベルの計算系を構成できます。例えば、トレース付きモノイド圏〈traced monoidal category〉のための計算系を構成できます。そのとき、ループ辺縮減がトレース〈trace〉を、非ループ辺縮減が結合〈composition〉を、頂点マージがモノイド積〈monoidal product〉を実現します。
- [BM06-11]
- Title: Generalized operads and their inner cohomomorphisms
- Authors: D. Borisov, Yu. I. Manin
- Submitted: 27 Sep 2006 (v1), 7 Jan 2011 (v5)
- Pages: 71p
- URL: https://arxiv.org/abs/math/0609748
- [Cos04-04]
- Title: The A-infinity operad and the moduli space of curves
- Author: Kevin Costello
- Submitted: 2 Feb 2004 (v1), 15 Sep 2004 (v2)
- Pages: 14p
- URL: https://arxiv.org/abs/math/0402015
- [BK22-]
- Title: Trees, graphs and aggregates: a categorical perspective on combinatorial surface topology, geometry, and algebra
- Authors: Clemens Berger, Ralph M. Kaufmann
- Submitted: 25 Jan 2022
- Pages: 48p
- URL: https://arxiv.org/abs/2201.10537
*1:半グラフ達とその変形達からなる圏に、因子分解系〈factorization system〉が存在するということです。
