Kontakt

+49 9131 85-27620

+49 9131 85-28809

Adresse

Universität Erlangen-Nürnberg
Informatik 2
Martensstr. 3
91058 Erlangen

Zimmer 05.137
Anfahrtsbeschreibung

Graphtransformationen

Das Gebiet der Graphgrammatiken und Graphtransformationen kombiniert Ideen aus den Bereichen Graphentheorie, Algebra, Logik und Kategorientheorie. Die breite Anwendbarkeit in verschiedenen Teilgebieten der Informatik resultiert aus der Tatsache, dass Graphen an vielen Stellen als intuitives Hilfsmittel zur Verdeutlichung komplizierter Sachverhalte verwendet werden, z.B. als Daten- bzw. Kontrollflussdiagramme, als Entity-Relationship-Diagramme, Petri-Netze, zur Visualisierung sowohl von Software- als auch von Hardware-Architekturen. Eine Graphgrammatik kann benutzt werden, um eine Menge syntaktisch korrekter Diagramme zu definieren, d.h. Diagramme, die nach den Regeln eines bestimmten Anwendungsgebietes aufgebaut sind. Graphtransformationen erlauben dynamische Veränderungen derartiger Darstellungen und somit die Beschreibung der Entwicklung von Strukturen.

• Der kategorielle Ansatz
  Dieser Ansatz ist ein attraktives Hilfsmittel, äußerst unterschiedliche Strukturen in einer einheitlichen Weise zu beschreiben. Seit 2002 konzentrierten sich unsere Arbeiten auf die einheitliche Beschreibung unterschiedlicher Modelle für asynchrone Prozesse. 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.
• Parallele Unabhängigkeit
  Die meisten Autoren diskutieren die Frage, ob zwei Ableitungsschritte vertauscht werden können, ohne das Ergebnis zu verändern, unter der strengen Voraussetzung, dass beide Seiten der Producktionen injektiv sind, obwohl der ursprüngliche Beweis nichtinjektive rechte Seiten erlaubt. Wir konnten zeigen, dass eine unwesentliche Einschränkung des Alphabets die Gültigkeit des Unabhängigkeitstheorems auch für Produktionen sichert, die die Markierungen ändern. Dieses Ergebnis kann in interessanten Bereichen angewandt werden, z.B. bei der Termgraphersetzung und bei Datenbankoperationen.
• Generizität
  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 beschreiben werden, die kategoriellen Eigenschaften können in einer Weise definiert werden, dass sie für alle Anwendungen gelten. Da moderne Programmiersprachen generische Konzepte unterstützen, liegt es nahe, den kategoriellen Ansatz in Sprachen wie Java und Haskell zu implementieren.

Ein Lehrbuch über dieses Gebiet ist in Vorbereitung.

Neuere Ergebnisse über Graphtransformationssysteme:

1. Implementing the Categorical Approach to Graph Transformations With Haskell
2. Changing Labels in the Double-Pushout Approach Can Be Treated Categorically
3. Relabeling and the Independence Theorem in the Double-Pushout Approach to Graph Transformations

Diese Aufsätze, das Lehrbuch und die Vorlesung sind mit einem Makro-Paket für LaTeX vorbereitet worden: Kurze Einführung (in German only) Macro-Defs

Sprechstunde: Im Anschluss an die Vorlesungen und außerdem nach Vereinbarung über E-Mail.

Vorlesungen

WS 2008/09:	Graphtransformationssysteme
	Vorauss. Mo 14-16 Uhr, Web-Seiten noch nicht aktuell
SS 2008:	Funktionale Programmierung mit Haskell
WS 2007/08:	(Anmerkungen zur) Geschichte der Programmiersprachen
SS 2007:	Prolog mit Anwendungen aus der linguistischen Informatik

Stellenangebote