Graph Transformations

Graph Transformations

An Introduction to the Categorical Approach

Hans Jürgen Schneider

Universität Erlangen-Nürnberg

At a workshop in Berlin (March 2000), some young participants critized the graph-transformation community for not having written a textbook that facilitates entering the field. I promised that I would do this after retiring. Now, drafts of two chapters are available.

  • Contents (PDF)
  • 1. Introduction (1st version) PDF
    The introduction includes historical remarks as well as some introductory examples.
  • 2. Categorical Notions (4rd Version) PDF
    In this chapter, we review the notions of category theory as far as we need them to describe graph transformations formally. We give some example categories the objects of which are (labeled) graphs or hypergraphs. We introduce colimits and study the properties of pushout diagrams.
  • 3. Derivability in Categories (4rd Version) PDF
    We define productions and derivation steps in a categorical setting without refering to graphs. Then, we apply these definitions to graphs. Interesting features arise from considering mappings that are not injective and/or do not preserve labels.
  • 4. Effectively Constructing Derivation Steps (3nd Version) PDF
    The main problem in constructing derivation steps effectively is completing a pushout diagram backwards. In this chapter, we show that the problem can be simplified by considering epimorphisms and monomorphisms separately.
  • 5. Operations on Derivation Sequences (3nd Version) PDF
  • 6. Related Topics (2nd version) PDF
  • References (PDF)
  • Index (PDF)
  • Appendix A: Implementing the Categorical Approach to Graph Transformations With Haskell (PDF)
  • Appendix B: Implementing the Categorical Approach to Graph Transformations With Java (PDF)
  • Appendix C: Graph Transformation by Computational Category Theory (PDF)
    (A Java-version using generics)
watermark seal