ダブルプッシュアウトグラフ書き換え

コンピュータサイエンスにおいて、二重プッシュアウトグラフ書き換え（またはDPOグラフ書き換え）は、グラフ書き換えの数学的枠組みを指します。これは、論文「グラフ文法：代数的アプローチ」（1973年）で、グラフ書き換えに対する最初の代数的アプローチの1つとして導入されました。^[1]その後、グラフではない書き換え構造を許可したり、負の適用条件を処理できるように一般化され、^[2]その他の拡張が行われました。

意味

DPOグラフ変換システム（またはグラフ文法）は、開始状態である有限グラフと、導出規則として機能する有限グラフおよびグラフ準同型のカテゴリ内のラベル付きスパンの有限または可算な集合で構成される。規則スパンは一般に単射で構成されるとされるが、詳細は変化することがある。^[3]

書き換えは、削除と追加の 2 つのステップで実行されます。

左側からへの一致が修正された後、右側にないノードとエッジは削除されます。次に、右側が接着されます。 $G$

グラフの接着は、実際にはグラフのカテゴリにおけるプッシュアウト構築であり、削除はプッシュアウト補集合を見つけることと同じであるため、この名前が付けられています。

用途

ダブルプッシュアウトグラフ書き換えでは、固定サイズと構成のパターンを指定して検索および置換することで、パターンの一部を保存できるグラフ変換を指定できます。ルールの適用は潜在的に非決定的であり、複数の異なる一致が考えられます。これらは重複しないか、保存された項目のみを共有し、並列独立性と呼ばれる一種の同時実行性を示します。 ^[4]または互換性がない可能性があり、その場合、アプリケーションが順番に実行されるか、一方が他方を排除することさえあります。

これはソフトウェア設計やプログラミング言語として使用できます（通常はグラフよりも豊富な構造で動作する変種が選択されます）。DPOグラフ書き換えの停止性は、ポスト対応問題がそれに還元できるため、決定不可能です。^[5]

DPOグラフ書き換えはペトリネットの一般化として見ることができる。^[4]

一般化

DPO書き換えが機能するカテゴリを記述するための公理が求められてきました。1つの可能性は、多くの閉包特性も備えた接着カテゴリの概念です。関連する概念には、HLRシステム、準接着カテゴリ、 -接着カテゴリ、接着HLRカテゴリがあります。[ ^6] ${\mathcal {M}}$

接着カテゴリーとHLRシステムの概念は関連している（副産物を持つ接着カテゴリーはHLRシステムである^[7]）。

例えば、ハイパーグラフ、型付きグラフ、属性付きグラフ書き換え^{[8]は、接着HLRシステムとしてキャストできるため、処理できます。}

注記

^ Hartmut Ehrig、Michael Pfender、Hans-Jürgen Schneider (1973 年 10 月)。「グラフ文法: 代数的アプローチ」。IEEE会議記録、第 14 回スイッチングおよびオートマトン理論シンポジウム( SWAT'08 )。IEEE。pp. 167–180。doi :10.1109/SWAT.1973.11。
^ Hartmut Ehrig、Karsten Ehrig、Annegret Habel、Karl-Heinz Pennemann (2004)。「制約とアプリケーション条件: グラフから高レベル構造へ」。Ehrig H.、Engels G.、Parisi-Presicce F.、Rozenberg G. (編)。グラフ変換。コンピュータサイエンスの講義ノート。第 3256 巻。Springer。pp. 287–303。doi :10.1007/ 978-3-540-30203-2_21。ISBN 978-3-540-23207-0。
^ 「ダブルプッシュアウトグラフ変換の再考」、Habel, Annegret、Müller, Jürgen、Plump, Detlef、『Mathematical Structures in Computer Science』、第 11 巻、第 05 号、637 ～ 688 ページ、2001 年、ケンブリッジ大学出版局
^ ab 「並行コンピューティング: ペトリネットからグラフ文法まで」、コラディーニ、アンドレア、ENTCS、第 2 巻、pp. 56--70、1995 年、エルゼビア
^ , 「グラフ書き換えの終了は決定不能である」、Detlef Plump、Fundamenta Informaticae、vol. 33、no. 2、pp. 201--209、1998、IOS Press
^ Hartmut Ehrig、Annegret Habel、Julia Padberg、Ulrike Prange、「接着剤の高レベル交換カテゴリーとシステム」、2004 年、Springer
^ 「接着カテゴリ」、Stephen Lack および Paweł Sobociński、『ソフトウェア科学と計算構造の基礎』、pp. 273--288、Springer 2004
^ 「代数グラフ変換の基礎」、Hartmut Ehrig、Karsten Ehrig、Ulrike Prange、Gabriele Taentzer

[ehrig73-1] Hartmut Ehrig、Michael Pfender、Hans-Jürgen Schneider (1973 年 10 月)。「グラフ文法: 代数的アプローチ」。IEEE会議記録、第 14 回スイッチングおよびオートマトン理論シンポジウム( SWAT'08 )。IEEE。pp. 167–180。doi :10.1109/SWAT.1973.11。

[ehrig2-2] Hartmut Ehrig、Karsten Ehrig、Annegret Habel、Karl-Heinz Pennemann (2004)。「制約とアプリケーション条件: グラフから高レベル構造へ」。Ehrig H.、Engels G.、Parisi-Presicce F.、Rozenberg G. (編)。グラフ変換。コンピュータサイエンスの講義ノート。第 3256 巻。Springer。pp. 287–303。doi :10.1007/ 978-3-540-30203-2_21。ISBN 978-3-540-23207-0。

[habel01-3] 「ダブルプッシュアウトグラフ変換の再考」、Habel, Annegret、Müller, Jürgen、Plump, Detlef、『Mathematical Structures in Computer Science』、第 11 巻、第 05 号、637 ～ 688 ページ、2001 年、ケンブリッジ大学出版局

[corradini-4] 「並行コンピューティング: ペトリネットからグラフ文法まで」、コラディーニ、アンドレア、ENTCS、第 2 巻、pp. 56--70、1995 年、エルゼビア

[plump1998termination-5] , 「グラフ書き換えの終了は決定不能である」、Detlef Plump、Fundamenta Informaticae、vol. 33、no. 2、pp. 201--209、1998、IOS Press

[ahlr-6] Hartmut Ehrig、Annegret Habel、Julia Padberg、Ulrike Prange、「接着剤の高レベル交換カテゴリーとシステム」、2004 年、Springer

[Lack-7] 「接着カテゴリ」、Stephen Lack および Paweł Sobociński、『ソフトウェア科学と計算構造の基礎』、pp. 273--288、Springer 2004

[8] 「代数グラフ変換の基礎」、Hartmut Ehrig、Karsten Ehrig、Ulrike Prange、Gabriele Taentzer