**Wolfram Kahl**

Habilitationsschrift 2001

Fakultät für Informatik

Universität der Bundeswehr München

Technical Report Nr. 2002-03, iv+204 pages

Fakultät für Informatik

Universität der Bundeswehr München

June 2002

Graph transformation is a rapidly expanding field of research, motivated by a wide range of applications.

Such transformations can be specified at different levels of abstraction. On one end, there are ``programmed'' graph transformation systems with very fine control over manipulation of individual graph items. Different flavours of rule-based graph transformation systems match their patterns in more generic ways and therefore interact with the graph structure at slightly higher levels.

A rather dominant approach to graph transformation uses the abstractions of category theory to define matching and replacement almost on a black-box level, using easily understandable basic category-theoretic concepts, like pushouts and pullbacks. However, some details cannot be covered on this level, and most authors refrain from resorting to the much more advanced category-theoretic tools of topos theory that are available for graphs, too - topos theory is not felt to be an appropriate language for specifying graph transformation.

In this thesis we show that the language of relations can be used very naturally to cover all the problems of the categoric approach to graph transformation. Although much of this follows from the well-known fact that every graph-structure category is a topos, very little of this power has been exploited before, and even surveys of the categoric approach to graph transformation state essential conditions outside the category-theoretic framework.

One achievement is therefore the capability to provide descriptions of all graph transformation effects on a suitable level of abstraction from the concrete choice of graph structures.

Another important result is the definition of a graph rewriting approach where relational matchings can match rule parameters to arbitrary subgraphs, which then can be copied or deleted by rewriting. At the same time, the rules are still as intuitive as in the double-pushout approach, and there is no need to use complicated encodings as in the pullback approaches.

In short: A natural way to achieve a double-pushout-like rewriting concept that incorporates some kind of ``graph variable'' matching and replication is to amalgamate pushouts and pullbacks, and the relation-algebraic approach offers appropriate abstractions that allow to formalise this in a fully component-free yet intuitively accessible manner.

- 1. Introduction
- 2. Graph Structures and Their Parts
- 3. Allegories of Σ-Algebras
- 4. Dedekind Categories of Graph Structures
- 5. Categoric Rewriting in a Relational Setting
- 6. Relational Rewriting in Dedekind Categories
- 7. Conclusion and Outlook
- Bibliography
- A. Proofs of Auxiliary Properties
- B. Proofs for Relational Rewriting, Chapter 6
- Index

- BibTeX entry
- Hyperlinked PDF (2.14 MB - for reasons I do not understand, some internal links lead to the wrong places)
- PostScript for printing on A4 paper (5.3MB), gzipped PostScript (1.44MB)
- 2-up PostScript for printing on A4 paper (8.5MB), the same gzipped (1.85MB).
- 2-up PostScript for printing on letter paper (8.5MB), the same gzipped (1.85MB).