バイグラフ

バイグラフは、グラフ（リンクグラフ）と木の集合（場所グラフ）の重ね合わせとしてモデル化できます。^{[1] [2]}

バイグラフの各ノードはグラフの一部であり、ノードがどのようにネストされているかを説明するツリーの一部でもあります。バイグラフは、図として便利かつ形式的に表示できます。^[1]ユビキタスコンピューティングの分散システムのモデリングに応用でき、モバイルインタラクションの記述にも使用できます。ロビン・ミルナーは、バイグラフを使用して、通信システム計算(CCS) とπ計算を統合しようとしました。^{[2]バイグラフは、}カテゴリ理論の文脈で研究されてきました。^{[3] [4]}

ノードと (ハイパー)エッジの他に、バイグラフには、プレース フォレストのルートである 1 つ以上の領域と、他のバイグラフ領域を挿入できるプレース グラフの0 個以上のホールが関連付けられている場合があります。同様に、ノードには、アイデンティティとアリティ (リンク グラフ エッジが接続できる特定のノードのポートの数) を定義するコントロールを割り当てることができます。これらのコントロールは、バイグラフシグネチャから取得されます。リンク グラフでは、内部名と外部名を定義します。これらは、一致する名前を融合して 1 つのリンクを形成できる接続ポイントを定義します。

バイグラフは 5 つの要素から構成されます。

${\displaystyle (V,E,ctrl,prnt,link):\langle k,X\rangle \to \langle m,Y\rangle ,}$

ここで、はノードのセット、はエッジのセット、はノードにコントロールを割り当てるコントロール マップ、はノードのネストを定義する親マップ、はリンク構造を定義する リンク マップです。${\displaystyle V}$${\displaystyle E}$${\displaystyle ctrl}$${\displaystyle prnt}$${\displaystyle link}$

この表記は、バイグラフに穴（サイト）と内部名と領域のセット、外部名のセットがあることを示しています。これらはそれぞれ、バイグラフの 内部インターフェイスと外部インターフェイスと呼ばれます。${\displaystyle \langle k,X\rangle \to \langle m,Y\rangle }$${\displaystyle k}$ ${\displaystyle X}$${\displaystyle m}$ ${\displaystyle Y}$

正式に言えば、各バイグラフは対称部分モノイドカテゴリ（通常spmカテゴリと略される）内の矢印であり、そのオブジェクトはこれらのインターフェイスです。^[5] その結果、バイグラフの合成はカテゴリ内の矢印の合成によって定義できます。

有向バイグラフ^[7]は、リンクグラフのハイパーエッジが有向であるバイグラフの一般化です。ポートとインターフェースの名前は、ハイパーエッジの方向が負から正に向かうという要件で極性（正または負）で拡張されます。

有向バイグラフは、位置とリソース通信を扱う計算パラダイムを記述するためのメタモデルとして導入されました。有向リンクグラフは、リソースの依存関係や情報の流れを自然に記述します。応用分野の例としては、セキュリティプロトコル、^[8]リソースアクセス管理、^[9]クラウドコンピューティングなどがあります。^[6]

共有付きバイグラフ^[10]は、ミルナーの形式化を一般化したものであって、空間的な位置の重なりや交差を直接的に表現できるものである。共有付きバイグラフでは、場所グラフは有向非巡回グラフ(DAG)として定義される。つまり、マップではなく二項関係である。共有の導入によってリンクグラフの定義は影響を受けない。標準バイグラフは共有付きバイグラフのサブクラスである点に注意されたい。 ${\displaystyle prnt}$

共有機能付きバイグラフの応用分野としては、無線ネットワークプロトコル^[11] 、国内無線ネットワークのリアルタイム管理^[12]、複合現実システム^[13]などが挙げられる。

• BigraphERは、OCamlライブラリとコマンドラインツールから構成されるバイグラフのモデリングおよび推論環境であり、バイグラフと共有バイグラフの両方の書き換え、シミュレーション、視覚化の効率的な実装を提供します。 ^[14]
• jLibBigは、バイグラフと有向バイグラフの両方に対して、バイグラフィカルリアクティブシステムの効率的で拡張可能な実装を提供するJavaライブラリです。 ^{[15] [16]}

積極的に開発されなくなったもの:

• BigMCはコマンドラインインターフェースと視覚化機能を備えたバイグラフのモデルチェッカーです。 ^[17]
• Big Redは、さまざまなファイル形式を簡単に拡張できるバイグラフ用のグラフィカルエディタです。^[18]
• SBAMは、生物学的モデルのシミュレーションを目的としたバイグラフの確率的シミュレータである。^[19]
• DBAMはバイグラフィカルリアクティブシステム用の分散シミュレータです。^[20]
• DBtkは、IPOの計算、マッチング、視覚化を提供する有向バイグラフ用のツールキットです。^[21]

• バイシミュレーション
• 組み合わせ種

• ミルナー、ロビン（2009）。コミュニケーションエージェントの空間と動き。ケンブリッジ大学出版局。ISBN 978-0521738330。
• Milner, Robin (2001)。「バイグラフィカル リアクティブ システム (招待論文)」。CONCUR 2001 – 並行性理論、第 12 回国際会議議事録。コンピュータ サイエンスの講義ノート。第 2154 巻。Springer -Verlag。pp . 16–35。doi : 10.1007/3-540-44685-0_2。
• Milner, Robin (2002)。「モバイルインタラクションのモデルとしてのバイグラフ (招待論文)」。ICGT 2002: グラフ変換に関する第 1 回国際会議。コンピュータサイエンスの講義ノート。第 2505 巻。Springer-Verlag。pp. 8–13。doi : 10.1007/3-540-45832-8_3。
• ドゥボワ、ソーレン。ダムガード、トロエルズ・クリストファー (2005)。 「例による伝記」。IT大学テクニカルレポートシリーズ TR-2005-61。デンマーク:コペンハーゲンIT大学。CiteSeerX  10.1.1.73.176。ISBN 978-87-7949-090-1。
• Sevegnani, Michele; Calder, Muffy (2015). 「共有機能付きバイグラフ」理論計算機科学577 : 43–73. doi : 10.1016/j.tcs.2015.02.011 .

• Bigraphs の書誌