Graphen und Graphtransformationen

Projektleitung:Schneider, H.
Zeitraum:1. Oktober 2004 - 31. Dezember 2014
Beschreibung:

Graphen werden an vielen Stellen als intuitives Hilfsmittel zur Verdeutlichung komplizierter Sachverhalte verwendet. Außerhalb der Informatik trifft dies z.B. auf die Chemie zu, wo Moleküle graphisch modelliert werden. Innerhalb der Informatik werden beispielsweise Daten- bzw. Kontrollflussdiagramme, Entity-Relationship-Diagramme oder Petri-Netze zur Visualisierung sowohl von Software- als auch von Hardware-Architekturen verwendet. Graphgrammatiken und Graphtransformationen kombinieren Ideen aus den Bereichen Graphentheorie, Algebra, Logik und Kategorientheorie, um Veränderungen an Graphen formal zu beschreiben.

Die Kategorientheorie ist ein attraktives Hilfsmittel, äußerst unterschiedliche Strukturen in einer einheitlichen Weise zu beschreiben, z.B. die unterschiedlichen Modelle für asynchrone Prozesse: Petri-Netze basieren auf gewöhnlichen markierten Graphen, Statecharts verwenden hierarchische Graphen, die parallele logische Programmierung kann mit Hilfe sogenannter Dschungel graphentheoretisch interpretiert werden, und die Aktorsysteme lassen sich als Graphen darstellen, deren Markierungsalphabet eine Menge von Termgraphen ist.

In letzter Zeit haben wir uns auf einen theoretischen Aspekt konzentriert.
Unsere Arbeiten zu den Graphtransformationen basieren auf Konzepten der Kategorientheorie. Der sogenannte Doppelpushout-Ansatz stellt eine Produktion durch zwei Morphismen dar, die an einem gemeinsamen Interface-Graphen ansetzen. Das eine Pushout fägt die linke Seite der Produktion in den Kontext ein, das andere die rechte Seite. Wenn wir einen Ableitungsschritt tatsächlich konstruieren wollen, müssen wir auf der linken Seite ein Pushout-Komplement finden, was als nachteilig empfunden wird. Raoult hat 1984 vorgeschlagen, die Graphersetzung durch ein einzelnes Pushout zu beschreiben; der Ansatz wurde dann von Loewe ausführlich diskutiert, wobei die Untersuchungen weitgehend auf injektive Morphismen beschränkt blieben. Unter dieser Voraussetzung sind die Ansätze äquivalent. Jedoch führen einige Anwendungen, z.B. die Termersetzung, zu nichtinjektiven Morphismen. Wir haben diese Fälle detailliert untersucht und konnten zeigen, dass sie auch in diesem Fall äquivalent sind, solange die Einbettung vernünftige Eigenschaften hat.

watermark seal