Graphen und GraphtransformationenGraphen 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. | Projektleitung: Prof. em. Dr. Hans Jürgen Schneider
Laufzeit: 1.10.2004 - 31.12.2014
Kontakt: Schneider, Hans Jürgen Telefon +49-9131-85-27620, Fax +49-9131-85-28809, E-Mail: hans.juergen.schneider@fau.de
|