Graph Transformation

This area deals with the manipulation of (labelled, directed) graphs of arbitrary shape by rules, combining the strengths of graphs and rules into a single computational model. Graphs are ubiquitous in computer science, representing and visualizing relationships between objects. Transformation rules allow a declarative way of computing, with simple syntax and semantics.

Research at York focuses on (1) fundamental properties of graph transformation systems, such as termination and confluence, (2) the application of graph transformation to safe pointer programming in languages such as C (Safe Pointers by Graph Transformation) and (3) the development, implementation and analysis of the GP programming language which combines graph transformation rules with control constructs.

Example: recognition of a balanced binary tree by graph reduction (rules not shown)
Slides of an introductory talk (focusing on confluence)
Graph Transformation and Graph Grammars Home Page

Handbook of Graph Grammars and Computing by Graph Transformation (World Scientific)

Volume 1: Foundations
ed. G. Rozenberg, 1997
Volume 2: Applications, Languages and Tools
eds. H. Ehrig, G. Engels, H.-J. Kreowski and G. Rozenberg, 1999
Volume 3: Concurrency, Parallelism and Distribution
eds. H. Ehrig, H.-J. Kreowski, U. Montanari and G. Rozenberg, 1999

Textbook

H. Ehrig, K. Ehrig, U. Prange, G. Taentzer: Fundamentals of Algebraic Graph Transformation. Springer-Verlag, 2006

Conferences and Workshops

ICGT 2010 - Fifth International Conference on Graph Transformation
Enschede (The Netherlands), September 27 - October 2, 2010

GT-VMT 2010 - Ninth International Workshop on Graph Transformation and Visual Modeling Techniques
Paphos (Cyprus), March 20-21, 2010

ICGT 2008 - Fourth International Conference on Graph Transformation
Leicester (United Kingdom), September 7-13, 2008

AGTIVE 2007 - Third International Workshop and Symposium on Applications of Graph Transformation with Industrial Relevance, Kassel (Germany), October 10-12, 2007