Contact

+49 9131 85-27620

+49 9131 85-28809

Address

University of Erlangen-Nuremberg
Chair 2 in Computer Science
Martensstr. 3
91058 Erlangen
Germany

Room 05.137
Driving directions

Graph Transformations

The research area of graph grammars and graph transformations combines ideas from graph theory, algebra, logic, and category theory. Its wide applicability in many areas of computer science is due to the fact that graphs are a very natural way to explain complex situations on an intuitive level. You find them in computer science almost everywhere, e.g., data- and control flow diagrams, entity relationship diagrams, Petri nets, visualization of software and hardware architectures. A graph grammar can be used to define the set of syntactically correct diagrams in an application area, whereas graph transformation brings dynamics to all these descriptions and allows us to describe the evolution of structures.

• The categorical approach
  This approach has become an attractive means to model and to study very different structures in a uniform way. Since 2002, we have put emphasis on unifying the different graph-theoretic models that describe asynchronous processes. Petri nets are based on "usual" graphs, state-charts use hierarchical graphs, a graph-theoretic interpretation of parallel logic programming leads to "jungles", and actor systems may be represented by graphs with a set of term graphs as the labeling alphabet.
• Parallel Independence
  Most authors discuss the question of whether two derivation steps can be exchanged without affecting the result under the strong assumptions that both sides of the productions are injective, although the original proof did allow noninjective right-hand sides. We could prove that a modest restriction to the structure of the alphabet guarantees the validity of the independence theorem even for productions that change labels. This result can be applied to interesting areas, e.g., term graph rewriting and data base operations.
• Genericity
  The categorical approach to graph transformations is highly generic: All the proofs and constructions are valid for various types of graphs. Only the basic operations must be described for each application in detail, the categorical properties can be defined in such a way that they hold for all applications. Since modern programming languages support generic concepts, it is promising to implement the categorical approach in languages lika Java and Haskell.

A textbook introducing this apporach is in preparation.

New results on graph transformation systems:

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

These papers as well as the textbook and the lecture are prepared using a LaTeX macro package: Kurze Einführung (in German only) Macro-Defs

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

Lectures (Information in German only. Sorry!)

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

Jobs