Double Pushout Graph Umschreiben - Double pushout graph rewriting

In der Informatik , Doppel Pushout- Graph Umschreiben bezieht (oder DPO Graph Rewriting) auf einen mathematischen Rahmen für Graph Rewriting . Es wurde als einer der ersten algebraischen Ansätze zum Umschreiben von Graphen in dem Artikel "Graph-Grammatiken: Ein algebraischer Ansatz" (1973) eingeführt. Es wurde seitdem verallgemeinert, um das Umschreiben von Strukturen, die keine Diagramme sind, zu ermöglichen und unter anderem negative Anwendungsbedingungen zu behandeln.

Definition

Ein DPO-Graphentransformationssystem (oder eine Graphgrammatik ) besteht aus einem endlichen Graphen , der den Ausgangszustand darstellt, und einem endlichen oder zählbaren Satz von markierten Bereichen in der Kategorie der endlichen Graphen und Graphenhomomorphismen, die als Ableitungsregeln dienen. Es wird allgemein angenommen, dass die Regelbereiche aus Monomorphismen bestehen , die Details können jedoch variieren.

Das Umschreiben erfolgt in zwei Schritten: Löschen und Hinzufügen.

Nachdem eine Übereinstimmung von der linken Seite zu behoben wurde, werden Knoten und Kanten gelöscht, die sich nicht auf der rechten Seite befinden. Die rechte Seite wird dann eingeklebt.

Das Kleben von Graphen ist in der Tat eine Pushout- Konstruktion in der Kategorie der Graphen, und das Löschen entspricht dem Finden eines Pushout-Komplements, daher der Name.

Verwendet

Das doppelte Umschreiben von Pushout-Diagrammen ermöglicht die Angabe von Diagrammtransformationen, indem ein Muster mit fester Größe und Zusammensetzung angegeben und ersetzt wird, wobei ein Teil des Musters beibehalten werden kann. Die Anwendung einer Regel ist möglicherweise nicht deterministisch: Es können mehrere unterschiedliche Übereinstimmungen möglich sein. Diese können sich nicht überlappen oder nur konservierte Elemente gemeinsam nutzen, wodurch eine Art Parallelität angezeigt wird, die als parallele Unabhängigkeit bezeichnet wird, oder sie können inkompatibel sein. In diesem Fall können entweder die Anwendungen manchmal nacheinander ausgeführt werden oder eine kann sogar die andere ausschließen.

Es kann als Sprache für das Software-Design und die Programmierung verwendet werden (normalerweise wird eine Variante gewählt, die an reicheren Strukturen als Graphen arbeitet). Kündigung für DPO Graph Rewriting ist unentscheidbar , weil der Beitrag Korrespondenzproblem es reduziert werden kann.

Das Umschreiben von DPO-Graphen kann als Verallgemeinerung von Petri-Netzen angesehen werden .

Verallgemeinerung

Axiome wurden gesucht, um Kategorien zu beschreiben, in denen das Umschreiben von Datenschutzbeauftragten funktionieren wird. Eine Möglichkeit ist der Begriff einer Klebstoffkategorie , die auch viele Verschlusseigenschaften aufweist. Verwandte Begriffe sind HLR-Systeme, quasi-adhäsive Kategorien und -adhäsive Kategorien, adhäsive HLR-Kategorien.

Die Konzepte der Klebstoffkategorie und des HLR-Systems sind verwandt (eine Klebstoffkategorie mit Nebenprodukten ist ein HLR-System).

Beispielsweise können Hypergraphen , typisierte Diagramme und das Umschreiben von Attributdiagrammen behandelt werden, da sie als selbstklebende HLR-Systeme gegossen werden können.

Anmerkungen

  1. ^ Hartmut Ehrig; Michael Pfender; Hans-Jürgen Schneider (Oktober 1973). "Graph-Grammatiken: Ein algebraischer Ansatz" . IEEE-Konferenzbericht des 14. jährlichen Symposiums über Switching und Automatentheorie (SWAT'08) . IEEE. S. 167–180. doi : 10.1109 / SWAT.1973.11 .
  2. ^ Hartmut Ehrig; Karsten Ehrig; Annegret Habel; Karl-Heinz Pennemann (2004). "Einschränkungen und Anwendungsbedingungen: Von Grafiken zu übergeordneten Strukturen" . In Ehrig H.; Engels G.; Parisi-Presicce F.; Rozenberg G. (Hrsg.). Graphtransformationen. ICGT . Vorlesungsunterlagen in Informatik. 3256 . Springer. S. 287–303.
  3. ^ "Double-Pushout-Graphtransformation überarbeitet", Habel, Annegret und Müller, Jürgen und Plump, Detlef, Mathematical Structures in Computer Science, vol. 11, nein. 05., S. 637–688, 2001, Cambridge University Press
  4. ^ a b "Concurrent Computing: Von Petri-Netzen zu Graph-Grammatiken", Corradini, Andrea, ENTCS, vol. 2, S. 56–70, 1995, Elsevier
  5. ^ , "Die Beendigung des Umschreibens von Graphen ist unentscheidbar", Detlef Plump, Fundamenta Informaticae, vol. 33, nein. 2, S. 201–209, 1998, IOS Press
  6. ^ Hartmut Ehrig und Annegret Habel und Julia Padberg und Ulrike Prange, "Adhesive High-Level-Ersatzkategorien und -systeme", 2004, Springer
  7. ^ "Adhesive Categories", Stephen Lack und Paweł Sobociński, in Grundlagen der Softwarewissenschaft und Rechenstrukturen , S. 273-288, Springer 2004
  8. ^ "Grundlagen der algebraischen Graphentransformation", Hartmut Ehrig, Karsten Ehrig, Ulrike Prange und Gabriele Taentzer