Jahresberichte

Graphtransformationssysteme 2002-2011

Graphen werden an vielen Stellen als intuitives Hilfsmittel zur Verdeutlichung komplizierter Sachverhalte verwendet. Außerhalb der Informatik trifft dies z.B. auf die Linguistik, Biologie oder Chemie zu, wo die Struktur vonSätzen oder Molekülen graphisch modelliert werden. Innerhalb der Informatik werden Daten- bzw. Kontrollflussdiagramme, Entity-Relationship-Diagramme oder Petri-Netze häufig 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. Eine Graphgrammatik kann benutzt werden, um eine Menge syntaktisch korrekter Diagramme zu definieren, d.h. Diagramme, die nach den spezifischen Regeln eines Anwendungsgebietes aufgebaut sind. Graphtransformationen erlauben dynamische Veränderungen derartiger Darstellungen und somit die Beschreibung der Entwicklung von Strukturen.

Die zugrunde liegende Theorie 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.

2002

Im Jahre 2002 wurden die Arbeiten zur einheitlichen Beschreibung unterschiedlicher Modelle für asynchrone Prozesse fortgesetzt. Die Petri-Netze basieren auf "gewöhnlichen" 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. Im Zusammenhang mit der Wiederaufnahme der Vorlesung über Graphtransformationssysteme wurden gewisse Nebenläufigkeitsaussagen, z.B. die Erzeugung aller möglichen "Traces" eines Programms oder die Vertauschbarkeit von Schritten, so allgemein formuliert, dass die Sätze auf alle genannten Modelle in gleicher Weise anwendbar sind.

Die Vorlesung über funktionale Programmierung war Anlass, die früher für Miranda und Java geschriebenen Implementierungen kategorieller Konstruktionen nach Haskell zu übertragen. Entsprechende Berichte sind in Vorbereitung.

2003

Im Zusammenhang mit den Arbeiten an einem neuen Lehrbuch über den kategoriellen Ansatz wurde im Jahr 2003 vornehmlich an einer Vereinheitlichung der effektiven Konstruktion der Ableitungsschritte gearbeitet und insbesondere die Situation bei nichteindeutigen Pushout-Komplementen untersucht. Dabei stellte sich heraus, dass die früher von Rosen und Parisi-Presicce betrachteten Normierungen Spezialfälle einer allgemeinen Konstruktion sind: Man kennt alle denkbaren Lösungen, wenn man das in gewissem Sinne minimale Pushout-Komplement konstruieren kann.

2004

Im Doppel-Pushout-Ansatz wird die linke Seite einer Produktion üblicherweise als injektiv vorausgesetzt, da der nichtinjektive Fall zu mehrdeutigen Ergebnissen führt. Die Behandlung von Markierungsänderungen mit Hilfe eines strukturierten Alphabetes führt aber auch im injektiven Fall zu Mehrdeutigkeiten. Die meisten Autoren lösen dieses Problem, indem sie nur die Transformation des zugrundeliegenden Graphen kategoriell, die Markierungsänderung aber separat behandeln. Die Arbeiten im Jahr 2004 dienten einer kategoriellen Charakterisierung aller Lösungen, wobei auf ein Ergebnis von Kreowski und Ehrig aus dem Jahre 1976 zurückgegriffen wurde. Es konnte gezeigt werden, dass damit wichtige Anwendungsgebiete (Petri-Netze, Termgraphen, Datenbanken) abgedeckt werden.

Mit Hilfe von Graphtransformationen werden nicht nur allgemeine Graphen generiert und analysiert, auch auf Zeichenketten basierende Sprachen und ihre Probleme können bearbeitet werden. Ein typisches Beispiel ist die kontextsensitive Sprache a^n b^n c^n. Sie kann mit kontextfreien Ersetzungsgrammatiken für Hyperkanten modelliert werden. Um mit diesen Hypergraphgrammatiken arbeiten zu können, wurde ein Parser entwickelt, der dem allgemeinen Earley-Parser ähnlich ist. Im Vergleich zum ursprünglichen Earley-Algorithmus wurde das Konzept der inaktiven Elemente erweitert. Ein Element wird nicht erst inaktiv, wenn es alle seine Komponenten gefunden hat, sondern kann auch an anderen Stellen inaktiv werden und so die Weiterverarbeitung ermöglichen. Die neue Variante des Predictor sorgt dafür, dass zwischenzeitlich inaktive Kanten, wieder zu aktiven umgewandelt werden.

2005

Im Doppel-Pushout-Ansatz wird die linke Seite einer Produktion üblicherweise als injektiv vorausgesetzt, da der nichtinjektive Fall zu mehrdeutigen Ergebnissen führt. Die Behandlung von Markierungsänderungen mit Hilfe eines strukturierten Alphabetes führt aber auch im injektiven Fall zu Mehrdeutigkeiten. Eine bekannte Lösung für dieses Problem ist, nur die Transformation des zugrundeliegenden Graphen kategoriell, die Markierungsänderung aber separat behandeln. Im Gegensatz zu diesem Ansatz konnten wir alle Lösungen kategoriell charakterisieren, wobei auf ein Ergebnis von Kreowski und Ehrig aus dem Jahre 1976 zurückgegriffen wurde. Es konnte gezeigt werden, dass damit wichtige Anwendungsgebiete (Petri-Netze, Termgraphen, Datenbanken) abgedeckt werden. Dieses Ergebnis wurde in der "Ehrig-Festschrift" veröffentlicht:
http://www2.informatik.uni-erlangen.de/Personen/schneide/hebook.pdf

Wenn zwei oder mehr Produktionen auf einen Graphen angewandt werden können, kann das Ergebnis von der Reihenfolge der Anwendung abhängen, oder die zweite Produktion ist nicht mehr anwendbar, nachdem die erste angewandt wurde. Die meisten Autoren diskutieren das Kriterium zur Prüfung der Unabhängigkeit unter der strengen Voraussetzung, dass beide Seiten der Produktionen injektiv sind, obwohl der ursprüngliche Beweis nichtinjektive rechte Seiten zuließ. Wie einige Autoren explizit anmerken, genügt die Kategorie der strukturiert markierten Graphen der Unabhängigkeitsbedingung nicht. Wir konnten zeigen, dass eine unwesentliche Einschränkung der Struktur des Alphabets ausreicht, um die Gültigkeit des Unabhängigkeitstheorems für wichtige Anwendungen, wie Termgraphen und Datenbankanwendungen, zu garantieren.

Mit Hilfe von Graphtransformationen werden nicht nur allgemeine Graphen generiert und analysiert, auch auf Zeichenketten basierende Sprachen und ihre Probleme können bearbeitet werden. Ein typisches Beispiel ist die kontextsensitive Sprache a^n b^n c^n. Sie kann mit kontextfreien Ersetzungsgrammatiken für Hyperkanten modelliert werden. Um mit diesen Hypergraphgrammatiken arbeiten zu können, wurde ein Parser entwickelt, der dem allgemeinen Earley-Parser ähnlich ist. Im Vergleich zum ursprünglichen Earley-Algorithmus wurde das Konzept der inaktiven Elemente erweitert. Ein Element wird nicht erst inaktiv, wenn es alle seine Komponenten gefunden hat, sondern kann auch an anderen Stellen inaktiv werden und so die Weiterverarbeitung ermöglichen. Die neue Variante des Predictor sorgt dafür, dass zwischenzeitlich inaktive Kanten, wieder zu aktiven umgewandelt werden.

2006

Wenn zwei oder mehr Produktionen auf einen Graphen angewandt werden können, kann das Ergebnis von der Reihenfolge der Anwendung abhängen, oder die zweite Produktion ist nicht mehr anwendbar, nachdem die erste angewandt wurde. Die meisten Autoren diskutieren das Kriterium zur Prüfung der Unabhängigkeit unter der strengen Voraussetzung, dass beide Seiten der Produktionen injektiv sind, obwohl der ursprüngliche Beweis nichtinjektive rechte Seiten zuließ. Wie einige Autoren explizit anmerken, genügt die Kategorie der strukturiert markierten Graphen der Unabhängigkeitsbedingung nicht. Wir konnten zeigen, dass eine unwesentliche Einschränkung der Struktur des Alphabets ausreicht, um die Gültigkeit des Unabhängigkeitstheorems für wichtige Anwendungen, wie Termgraphen und Datenbankanwendungen, zu garantieren. Die Ergebnisse erscheinen im Bulletin of the European Association for Theoretical Computer Science (Feb. 2007):
http://www2.informatik.uni-erlangen.de/Personen/schneide/parindep.pdf

Der kategorielle Ansatz bei Graphtransformationen ist äußerst generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die aufgesetzten kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, ist es vielversprechend, den kategoriellen Graphtransformationsansatz in Sprachen wie Java und Haskell zu implementieren. Java benutzt Objektklassen, unterstützt aber nicht wirklich die Mehrfachvererbung, da in Interfaces keine Defaultmethoden erlaubt sind. Andererseits unterstützt Haskell Mehrfachvererbung, aber betrachtet Typklassen. Aus unserer Pilotimplementierung ergeben sich interessante Fragestellungen bezüglich der unterschiedlichen Bedeutung von Generizität.

Mit Hilfe von Graphtransformationen werden nicht nur allgemeine Graphen generiert und analysiert, auch auf Zeichenketten basierende Sprachen können bearbeitet werden. Insbesondere können kontextfreie Grammatiken zur Hyperkantenersetzung Sprachen behandeln, die in Chomskys Theorie nicht kontextfrei sind. Dieser Ansatz kann erfolgreich auf die Probleme diskontinuierlicher Konstituenten und der freien Wortstellung in natürlichen Sprachen angewandt werden. Z.B. haben Aussagesätze im Englischen eine feste Wortstellung (Subjekt, Verb, Objekte, Präpositionalphrasen), während im Ungarischen der Gebrauch von Wortendungen das Verstehen eines Satzes trotz der vollständig freien Wortordnung sichert. Wir haben eine Notation für Hypergraphproduktionen entwickelt, die es dem Benutzer ermöglicht, die Ordnung der Knoten einzuschränken, und die von HyperEarley, einem Parser für zeichenkettenerzeugende Hypergraphgrammatiken, analysiert werden kann. Die Ergebnisse wurden in den Proceedings of the Third International Conference on Graph Transformations (Natal, Brasilien, Sept. 2006) veröffentlicht:
http://www2.informatik.uni-erlangen.de/Forschung/Publikationen/download/riedl.pdf

2007

Der kategorielle Ansatz bei Graphtransformationen ist äußerst generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die aufgesetzten kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, ist es vielversprechend, den kategoriellen Graphtransformationsansatz in Sprachen wie Java und Haskell zu implementieren. Java benutzt Objektklassen, unterstützt aber nicht wirklich die Mehrfachvererbung, da in Interfaces keine Defaultmethoden erlaubt sind. Andererseits unterstützt Haskell Mehrfachvererbung, aber betrachtet Typklassen. Aus unserer Pilotimplementierung ergeben sich interessante Fragestellungen bezüglich der unterschiedlichen Bedeutung von Generizität. Die Haskell-Version ist bereits verfügbar:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-a.pdf

2008

Eine Datenbanktransaktion wird durch eine Sequenz atomarer Transformationen beschrieben, die aber von außen als unteilbarer Schritt angesehen wird. Aus der Sicht der Graphtransformationssysteme lautet die Frage: Können wir, wenn eine Ableitungssequenz gegeben ist, eine Produktion konstruieren, die die Wirkung der gesamten Ableitungssequenz in einem Ableitungsschritt simuliert? Die Fragestellung wurde bereits in unserem Einführungsaufsatz (1973) untersucht, aber beschränkt auf injektive Graphmorphismen. H. Ehrig und H.-J. Kreowski haben das Ergebnis 1976 auf markierte Graphen übertragen, und H. Ehrig erlaubte 1977 nichtinjektive Einbettungen, aber seine Darstellung verwendet mengentheoretische Argumente und macht keinen Gebrauch von den kategoriellen Konstruktionen. Im Jahr 2006 haben Ehrig et al. eine rein kategorielle Darstellung vorgelegt, die aber nur den Spezialfall der adhäsiven Kategorien betrachtet und sich ebenfalls auf Monomorphismen beschränkt. Jetzt konnten wir zeigen, dass diese restriktiven Einschränkungen unnötig sind. Unsere Lösung ist ebenfalls rein kategoriell, macht aber keinerlei Einschränkungen bei den Morphismen. Darüber hinaus verlangen wir nur, dass die betrachtete Kategorie Pushouts und Pullbacks besitzt; das bedeutet, dass wir das Ergebnis auf jede praktisch interessante Kategorie anwenden können, insbesondere auf die Kategorie der strukturiert markierten Graphen, die nicht adhäsiv ist. Der Beweis ist im Entwurf zu unserem Lehrbuch enthalten:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter5.pdf

Die kategorielle Behandlung der Graphtransformationen ist hochgradig generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die darauf aufbauenden kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, sieht es vielversprechend aus, den kategoriellen Ansatz zur Beschreibung von Graphtransformationssystemen in Sprachen wie Java oder Haskell zu implementieren. Java benutzt Klassen von Objekten, aber es unterstützt die Mehrfachvererbung nicht wirklich, da Schnittstellen (Interfaces) keine Methodendefinitionen enthalten dürfen. Deshalb müssen eigene Konstruktionsklassen (factory classes) eingeführt werden, die die generischen kategoriellen Konstruktionen implementieren und die von jeder implementierten Kategorie importiert werden müssen. Dagegen unterstützt Haskell die Mehrfachvererbung, betrachtet aber Klassen von Typen und verlangt, dass konkrete Typen explizit zu Instanzen aller Klassen gemacht werden müssen, zu denen sie gehören. Unsere Pilotimplementierungen werfen interessante Fragen bezüglich der unterschiedlichen Sicht von Generizität auf. Die Haskell-Version ist bereits verfügbar:
http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-a.pdf
Die Java-Version wird demnächst verfügbar sein. Die wesentlichen Teile sind jedoch in dem Begleitmaterial zur Vorlesung über Graphtransformationssysteme zu finden:
http://www2.informatik.uni-erlangen.de/Lehre/WS200809/GraTra/index.xml

2009

In den letzten Jahren haben wir das Konzept der unabhängigen Ableitungsschritte so verallgemeinert, dass es in jeder interessanten Kategorie, insbesondere in der Kategorie strukturiert markierter Graphen, angewandt werden kann. Wir haben nun die Untersuchungen zur Transformation von Ableitungssequenzen mit der Betrachtung paralleler Produktionen abgeschlossen, das sind Produktionen, die die Wirkung zweier oder mehrerer Produktionen in einem Schritt kombinieren. Es ist einfach, parallele Produktionen als Coprodukt mehrerer Produktionen zu definieren, aber im Fall der Graphen führt dies zu Ableitungsschritten, deren Einbettung nicht injektiv ist. Im Gegensatz zu anderen bekannten Ansätzen, sind unsere Untersuchungen nicht auf injektive Einbettungen beschränkt, und die Konstruktion ist somit ausreichend. Auf der Basis paralleler Ableitungsschritte kann man kanonische Ableitungen definieren. In der Theorie der Chomsky-Sprachen, benutzt diese Definition die Anordnung der Symbole von links nach rechts, die es bei Graphen nicht gibt. Kreowski hat 1976 eine Alternative vorgeschlagen: Unabhängige Ableitungsschritte werden zu parallelen zusammengefasst und die Komponenten auf die frühest mögliche Position verschoben. Eine kanonische Ableitung ist eine, in der keine Shift-Operationen mehr möglich sind. Kreowskis Definition kann unmittelbar auf unsere allgemeine, nicht auf Graphen beschränkte Darstellung übertragen werden. Die Details finden sich im Entwurf zu unserem Lehrbuch: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter5.pdf

Die kategorielle Behandlung der Graphtransformationen ist hochgradig generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die darauf aufbauenden kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, sieht es vielversprechend aus, den kategoriellen Ansatz zur Beschreibung von Graphtransformationssystemen in Sprachen wie Java oder Haskell zu implementieren. Java benutzt Klassen von Objekten, aber es unterstützt die Mehrfachvererbung nicht wirklich. In unserer ersten Version definieren wir Schnittstellen (Interfaces) Cat, CatWithColimits, usw. Die grundlegenden Colimites (Coprodukt, Coegalisator, initiales Objekt) werden als abstrakte Klassen eingeführt, deren Details von den speziellen Kategorien implementiert werden müssen. Da diese Colimites die Konstruktion aller anderen Colimites ermöglichen, wäre es sinnvoll, CatWithColimits mit einer Methode auszustatten, die Pushouts konstruiert, aber CatWithColimits ist ein Interface. Daher führen wir eine Klasse PushoutCreator ein, die die kategorielle Konstruktion unabhängig von einer speziellen Kategorie beschreibt. Jede Kategorie mit Colimites muss diese "Factory class" importieren. Eine zusammenfassende Darstellung dieser Version ist verfügbar: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/appendix-b.pdf

2010

Auch im Jahre 2010 haben wir sowohl theoretische Konzepte untersucht als auch einen Implementierungsaspekt betrachtet:

Im Mittelpunkt unserer Arbeiten über Graphtransformationen steht der sogenannte Doppelpushout-Ansatz, bei dem eine Produktion durch zwei Morphismen bestimmt wird, die an einem gemeinsamen Interface-Graphen ansetzen. Die Weiterarbeit an dem geplanten Lehrbuch hat dazu geführt, einige Alternativen zu analysieren und deren Beziehungen zum Doppelpushout-Ansatz zu studieren. Wir haben zunächst die Hyperkantenersetzung und die einwärts gerichteten Produktionen betrachtet. Die Hyperkantenersetzung dient der formalen Beschreibung sowohl von Berechnungen als auch von graphischen Darstellungen. In der Literatur wird sie üblicherweise nicht im Kontext des Doppelpushout-Ansatzes behandelt, weil die meisten Arbeiten über diesen nichtinjektive Abbildungen ausschließen. Unsere bisherigen Ergebnisse vermeiden diese Einschränkung, und deshalb passt die Hyperkantenersetzung zu dem Doppelpushout-Ansatz. Als Nebeneffekt finden wir eine Klasse kontextfreier Graphgrammatiken, die einige Sprachen umfassen, die als Zeichenkettengrammatiken nicht kontextfrei sind. Das zweite Thema basiert auf einem Vorschlag von Banach. Er hat die Richtung der Morphismen in der Produktion umgedreht, so dass sie nach Innen gehen und die linke und die rechte Seite in einen größeren Kontext einbetten. Dieser Ansatz erlaubt die Aufdeckung einiger interessanter Beziehungen zu operationellen (nicht-kategoriellen) Ansätzen, aber auch zu dem Ansatz der "adhesive grammar". Die Details werden in Kürze im Entwurf des Lehrbuches veröffentlicht: http://www2.informatik.uni-erlangen.de/Personen/schneide/gtbook/chapter6.pdf

Die kategorielle Behandlung der Graphtransformationen ist hochgradig generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die darauf aufbauenden kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, sieht es vielversprechend aus, den kategoriellen Ansatz zur Beschreibung von Graphtransformationssystemen in Sprachen wie Java oder Haskell zu implementieren. Im Jahre 2008 haben wir diesen Ansatz unter Ausnutzung des Polymorphismus in der funktionalen Sprache Haskell implementiert. Java benutzt Klassen von Objekten, unterstützt aber nicht wirklich die mehrfache Vererbung. In der Version von 2009 definieren wir Schnittstellen Cat, CatWithColimits usw, die durch Klassen wie beispielsweise CatFinSet oder CatFinGraph implementiert werden müssen. Diese Lösung erlaubt jedoch nicht, die Methode zur Konstruktion von Pushouts in CatWithColimits aufzunehmen. Deshalb haben wir eine separate "Factory"-Klasse PushoutCreator definiert, die die kategorielle Konstruktion unabhängig von einer speziellen Kategorie beschreibt und von den die speziellen Kategorien beschreibenden Klassen importiert werden muss. Jetzt haben wir eine Alternative implementiert, die auf den generischen Datentypen von Java basiert. Der Trick besteht darin, eine abstrakte Klasse CocoCat der covollständigen Kategorien zu definieren, die die kanonischen Konstruktionen der Colimites, z.B. des Pushouts, enthält und sie so den konkreten Unterklassen zur Verfügung stellt. Der entscheidende Nachteil dieser Vorgehensweise ist, dass die generischen Parameter bei allen Klassen und allen Methoden mitgeschleppt werden müssen. Eine Zusammenfassung dieser Implementierung ist zu finden in Engels et al. (Eds.): Graph Transformation and Model-Driven Engineering (Lect. Notes Comp. Sc. vol. 5765, 2010), pp. 33-58.

2011

Im Jahre 2011 haben wir uns auf einen theoretischen Aspekt konzentriert, während die Untersuchung der Implementierungsaspekt zu kurz kam.

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. Wenn wir die Konzepte der Kategorientheorie benutzen, können wir eine Reihe von Eigenschaften herleiten, ohne auf den speziellen Typ der Graphen oder des Markierungsmechanismus einzugehen. Die ersten Kapitel des geplanten Lehrbuches haben sehr verschiedene Arten von Graphen und unterschiedliche Markierungsmeschanismen behandelt, und wir mussten in jedem Fall beweisen, dass sie die erforderlichen Eigenschaften erfüllen. Im letzten Kapitel greifen wir die Arbeit von Schied auf, der das Konzept der Komma-Kategorie auf den Doppelpushout-Ansatz angewandt hat. Dann ist es ausreichend, die interessierenden Eigenschaften für einige Basiskategorien zu beweisen, da wir sie auf eine andere Kategorie übertragen können, indem wir diese als Komma-Kategorie von zwei geeigneten Funktoren definieren. Neue Ergebnisse betreffen (1) Kategorien, deren Morphismen Markierungen in einer wohldefinierten Weise ersetzen dürfen (strukturiert markierte Graphen), und (2) den Beweis, dass die sogenannte PIT-Eigenschaft für die Komma-Kategorie gilt, wenn der erste Funktor ko-stetig ist. (Kategorien, die die PIT-Eigenschaft erfüllen, erlauben ein einfaches Kriterium, um die Vertauschbarkeit von Ableitungsschritten zu überprüfen.)

Die kategorielle Behandlung der Graphtransformationen ist hochgradig generisch: Alle Beweise und Konstruktionen gelten für verschiedene Graphtypen. Nur die grundlegenden Operationen müssen für jede Anwendung detailliert beschrieben werden, die darauf aufbauenden kategoriellen Eigenschaften sind dann automatisch definiert. Da moderne Programmiersprachen generische Konzepte unterstützen, sieht es vielversprechend aus, den kategoriellen Ansatz zur Beschreibung von Graphtransformationssystemen in Sprachen wie Java oder Haskell zu implementieren. In den letzten Jahren haben wir dazu drei Versionen implementiert. Die Haskell-Version nutzt den Polymorphismus aus. Java erlaubt allerdings keine Mehrfachvererbung. Die erste Java-Version implementiert deshalb die kategoriellen Konstruktionen, wie zum Beispiel das Pushout, durch eigene Konstruktionsklassen (Factory-Klassen). Die zweite basiert auf den generischen Datentypen. Der nächste Schritt wird der Vergleich dieser Versionen im Hinblick auf ihre Vor- und Nachteile sein.

watermark seal