213 測定値新しい歴史

万物の代数

に Monograph6m2025/03/16

NSO

長すぎる; 読むには

モノグラフは、ノードを長さ 0 のエッジとして扱い、任意の長さのエッジを許可することでグラフを一般化します。モノグラフは代数グラフ変換の普遍的なフレームワークを形成し、型付きグラフや属性付きグラフに適用されます。

著者：

(1) ティエリー・ボーイ・ドゥ・ラ・トゥール大学グルノーブルアルプ、CNRS、グルノーブル INP、LIG 38000 グルノーブル、フランス。

リンク一覧

要約と1 はじめに

2 基本的な定義と表記

2.1 セット

2.2 シーケンス

2.3 署名と代数および 2.4 カテゴリ

抽象的な

モノグラフは、長さ無制限の有向エッジが自由に隣接しているグラフのような構造です。標準ノードは、長さ 0 のエッジとして表されます。標準グラフや、E グラフや 8 グラフなどの他の多くのグラフと一貫性のある方法で描画できます。モノグラフのカテゴリは、終端モノグラフがないことを除いて、グラフ構造のカテゴリ (モナド多ソートシグネチャの代数) と多くの特性を共有しています。モノグラフのスライスカテゴリ (または型付きモノグラフのカテゴリ) がグラフ構造のカテゴリと同等であるという意味で、モノグラフは普遍的です。したがって、型モノグラフは、グラフ構造を指定する自然な方法として登場します。モノグラフの単一および二重プッシュアウト変換の詳細な分析が提供され、型付き属性付き E グラフを一般化する属性付き型付きモノグラフの概念が、属性保存変換に関して分析されます。

キーワード: 代数的グラフ変換、グラフ構造、型付きグラフ

1 はじめに

数学やコンピュータサイエンスでは、単純グラフ、有向グラフ、マルチグラフ、ハイパーグラフなど、グラフのさまざまな概念が使用されています。論理と書き換えのコンテキストでよく使用される概念の 1 つは、quiver としても知られるものです。つまり、pN、E、s、tq の形式の構造です。ここで、N、E はセット、s、t は E (エッジ) から N (ノード) への関数であり、すべてのエッジ (または矢印) のソースチップとターゲットチップを識別します。この理由の 1 つは、quiver のカテゴリが、2 つのソートノードとエッジ、およびタイプエッジ - ノードの 2 つの演算子名 src と tgt を持つ、多ソートシグネチャの代数のカテゴリと同型であるためです。この伝統に従い、この論文ではグラフとは quiver を意味します。

複雑なデータ構造を便利に表現するためには、グラフの構造を属性で強化することがしばしば必要になります。ノードやエッジには、固定セットの要素、何らかの代数で取得された値、または [1] にあるような値のセットなどでラベル付けすることができます。属性もノードとして扱われるため、E グラフの概念を使った興味深い例が [2] にあります。

より正確には、E グラフは、そのシグネチャが次のグラフによって表される代数です。

ソートと演算子に付けられた名前は、E グラフの構造を理解するのに役立ちます。エッジはノード同士を関連付け、nv エッジはノードを値に関連付け、ev エッジはエッジを値に関連付けます。したがって、ソート値はノードでもある属性を保持します。ただし、E グラフでは ev エッジがエッジに隣接していることがわかります。これは標準ではありませんが、そのような構造を何らかのグラフ形式として受け入れることもできます。ただし、その描画方法がわかっているという理由だけでです。

したがって、グラフの概念を一般化する方法は、代数として考えられたグラフのシグネチャの一般化を伴うように思われる。この道は Michael L¨owe によって [3] で踏襲されており、グラフ構造はモナド多ソートシグネチャとして定義されている。確かに、上記の例や [3] で提供されている多くの例では、すべての演算子はアリティ 1 を持ち、したがってドメインから範囲ソートへのエッジと見なすことができます。これがグラフ構造と呼ばれる理由でしょうか。しかし、上記の例は、E グラフがそのシグネチャを表すグラフとは非常に異なることを示しています。さらに、このような構造の理解が構文、つまりシグネチャ内のソートと演算子に与えられた特定の名前に基づくのは便利ではありません。

さらに、非常に単純なモナドシグネチャの代数が、どのような形式のグラフとして解釈できるのか、理解するのは困難です。たとえば、グラフのシグネチャを取り、ターゲット関数を tgt : ノード Ñ エッジに反転します。すると、ノードとエッジのソートの間に対称性が生じます。つまり、このシグネチャの代数では、ノードとエッジは同じ性質のオブジェクトになります。これはまだグラフでしょうか。描くことはできますか。さらに悪いことに、2 つのソートが 1 つにまとめられる場合、ノード/エッジがそれ自体に隣接できることになりますか。

これらの問題に対処するには、たとえば明確に分離されたエッジとノードを示すなど、代数が正統的な方法で動作することが保証されているモナド署名のクラスにグラフ構造を制限する必要があります。しかし、これは恣意性に陥りやすく、グラフ構造の概念がカテゴリを簡単に生み出さないという別の欠点も残ります。実際、異なる署名の代数間の射を定義するのは、キャリアセットがいくつでも存在する可能性があるという理由だけでも困難です。

ここで採用されているアプローチは、むしろノードとエッジの構造的な区別を拒否し、したがってノードを長さ 0 のエッジ、標準エッジを 2 つのノードに隣接しているため長さ 2 のエッジと統一的に見なすことです。この統一的な見方では、論理的にエッジはノードだけでなく任意のエッジに隣接できるため、E グラフの ev エッジが一般化され、さらに自分自身に隣接するエッジにも一般化されます。最後に、エッジの長さを 0 または 2 に制限する理由はなく、無限の順序長のエッジを許可する十分な理由が (セクション 6 で) 見つかります。必要な概念と表記法はセクション 2 で導入されます。モノグラフの構造 (およびモルフィズム) はセクション 3 で定義され、いくつかの特性に応じてモノグラフのカテゴリのベストイアリが得られます。これらのカテゴリの極限と共極限の存在に関する特性は、セクション 4 で分析されます。

次に、セクション 5 で、モノグラフが有限個の辺を持ち、その辺の長さが有限であることを前提として、モノグラフを図面で正確に表現する方法を説明します。特に、このような図面は、標準グラフと同一視できるモノグラフの標準的なグラフ描画方法に対応しており、E グラフについても同様です。

第 6 節では、モノグラフとグラフ構造の比較、および対応する代数 (グラフ構造代数と呼ぶこともあります) について説明します。すべてのグラフ構造代数は (通常は標準的な方法ではありませんが) 型付きモノグラフ、つまりモノグラフのモルフィズムとして表現できるという意味で、モノグラフの普遍性という特性を示します。

[3] では、代数的グラフ書き換えの技術を実行できる部分準同型のカテゴリを取得するためにグラフ構造の概念が導入されました。セクション 6 で確立されたモノグラフとの対応により、セクション 7 でモノグラフの部分同型の同様の展開が必要になります。次に、セクション 8 でモノグラフ書き換えのシングルプッシュアウト法とダブルプッシュアウト法を定義、分析、比較します。

Eグラフの概念は[2]で導入され、属性付きグラフの適切なカテゴリ（グラフ書き換えに関して）を取得し、実際のデータ構造の適切な表現を提案することを目的としています。これは、Eグラフをデータ型代数で強化し、ソート値のノードをこの代数の要素で識別することによって実現されます。セクション9では、属性付き型付きモノグラフの概念を使用して、エッジを持つ代数の要素を識別することで同様のアプローチを追求し、同様に適切なカテゴリを取得します。モノグラフの普遍性により、任意のΣ-代数を属性付き型付きモノグラフとして表現できることがわかります。

第10節で結論を述べます。第4節から第6節の一部は[4]に掲載されていることに注意してください。