著者：  (1) ティエリー・ボーイ・ドゥ・ラ・トゥール大学グルノーブル アルプ、CNRS、グルノーブル INP、LIG 38000 グルノーブル、フランス。 リンク一覧 要約と1 はじめに 2 基本的な定義と表記 2.1 セット 2.2 シーケンス 2.3 署名と代数および 2.4 カテゴリ 3 モノグラフとそのモルフィズム 4 極限と余極限 5 ドローイング モノグラフ 6 グラフ構造と型付きモノグラフ 7 サブモノグラフと部分同型 8 モノグラフの代数変換 9 属性付きタイプ付きモノグラフ 10 結論と参考文献 抽象的な モノグラフは、長さ無制限の有向エッジが自由に隣接しているグラフのような構造です。標準ノードは、長さ 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]に掲載されていることに注意してください。 この論文は、CC BY 4.0 DEED ライセンスの下で 。 arxiv で公開されています

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Read My Stories

Monograph's in-depth journey delves into the soul, revealing the essence of a subject with precision and passion.

monograph's blog

このオーディオは、ストーリーの元の言語で制作されています。

万物の代数

About Author

コメント

ラベル

この記事は

Related Stories

目に見えない層: ユーザーインタビューがかけがえのない資産である理由

AI の力を解き放つ。最先端技術の体系的レビュー: 概要と序論

ユニークなエコシステムを支えるビットコインUTXOのモデル

フロキのヴァルハラがインドのスリランカツアーのアソシエイトスポンサーに加わる

目に見えない層: ユーザーインタビューがかけがえのない資産である理由

AI の力を解き放つ。最先端技術の体系的レビュー: 概要と序論

ユニークなエコシステムを支えるビットコインUTXOのモデル

フロキのヴァルハラがインドのスリランカツアーのアソシエイトスポンサーに加わる

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps