Workshop on Graph Computation Models 2008

GCM 2008

September 8, 2008 Leicester


A satellite workshop of ICGT 2008 

September 7 - 13, 2008, Leicester, UK



Call for papers          Program       Proceedings


Call for Papers

A variety of computation models have been developed using graphs and graph transformations. These models include features for programming languages and systems, paradigms for software development, concurrent calculi, local computations and distributed algorithms, biological or chemical computations. Graph transformations can be an intermediate representation of a computation. In addition to being visual and intuitive, this representation also allows the use of mathematical methods for analysis and manipulation. The aim of the workshop is to bring together researchers interested in all aspects of computation models based on graphs and graph transformation techniques, and their applications. A particular emphasis will be made for models and tools describing general solutions. The workshop will include contributed papers, tutorials and tool demonstrations.


Authors of contributed papers are invited to submit extended abstracts of 5 to 10 pages in LNCS format by May 30th (extended) June 13th, 2008. Submissions should be made via Easychair at the following address:




Mohamed Mosbah, University of Bordeaux 1, France

Annegret Habel, University of Oldenburg, Germany 



·        Frank Drewes, Umeå University, Sweden

·        Rachid Echahed, IMAG, Grenoble, France

·        Emmanuel Godard, University of Provence Aix-Marseille, France

·        Stefan Gruner, University of Pretoria, South Africa

·        Annegret  Habel, University of Oldenburg, Germany

·        Dirk Janssens, University of Antwerp, Belgium

·        Hans-Jörg Kreowski, University of Bremen, Germany

·        Mohamed Mosbah, University of Bordeaux 1, France

·        Detlef Plump, University of York, UK


30 May  13 June 2008

Paper submission deadline (extended)

5  July 2008

Notification of acceptance

15 July 2008

Final version due

8 September 2008




During the workshop, there will be a session where tools and ongoing works can be presented. 





Preliminary Program

Monday 8 September


09.00 - 10.00  Modelling computational and logistic processes by autonomous units

                    Hans-Jörg Kreowski, University of Bremen, Germany

 The notion of a community of autonomous units is a graph-transformational device for the modelling of computational and - in particular  - logistics processes that co-exist, run and interact in the same environment. The units may communicate and cooperate with each other, their process runs may be sequential, parallel, or concurrent. In the talk, the framework will be introduced and some computational aspects stressed.


10.30-11.30  From Actors to Aspects: Programming with Graph Transformations

Dirk Janssens, University of Antwerp, Belgium

 The obvious advantage of computational models that directly manipulate discrete structures or graphs is that  they allow one to work on a convenient level of abstraction, close to intuition about networks, object diagrams, or system states in general, and  avoiding cumbersome coding into strings or formulas. In Graph Transformation systems, one takes the view that the desired manipulations can be obtained though local changes, embodied by rules: not only is the application of rules controlled by pattern matching, but it is also assumed that the changes are restricted to the pattern; i.e. the part of the structure that is not involved in a rule application remains unchanged.

The tutorial gives an overview of opportunities and challenges related to the use of graph transformation as a model of computation. As a starting point, work concerning Actor languages is used, which is based on very simple mathematics and should hence be accessible to a public not acquainted with the existing theory of graph transformation. Then issues concerning concurrency and modularity are discussed, as well as the challenges caused by the need to introduce more control and genericity than present in the basic mechanism.

Finally we discuss how proposed solutions to these challenges are used in recent work about refactoring and model transformation, and we outline some further potential applications to aspect-oriented or delegation-based languages, as well as to topics outside of traditional computing science, such as self-assembly or natural computing.


11.30–12.30 Contributions  


       Graph Rewrite Rules with Structural Recursion

         Berthold Hoffmann, Edgar Jakumeit and Rubino Geiß


        Assuring Termination of Control Conditions for Graph Transformation Systems by Means of Petri Nets   

        Renate Klempien-Hinrichs and Melanie Luderer



12.30-14.00 Lunch


14.00-15.00  An Introduction to GP

       Detlef Plump, The University of York

GP is a rule-based, nondeterministic programming language for solving graph problems at a high level of abstraction, freeing programmers from dealing with low-level data structures. GP's design aims at syntactic and semantic simplicity, to facilitate formal reasoning about programs. The language core consists of just four constructs: single-step application of a set of graph-transformation rules, sequential composition, branching and looping. This talk introduces GP by a number of example programs, presents a formal semantics in the style of Plotkin's structural operational semantics, and briefly describes the current implementation. Particular attention will be given to GP's powerful branching and looping constructs which allow to hide destructive tests and to iterate arbitrary subprograms.

15.00-16.00        Short Contributions


Parallel Graph Transformations in Distributed Adaptive Design   

Leszek Kotulski and Barbara Strug


Editing Nested Constraints and Application Conditions   

Karl Azab


Efficient Graph Rewriting System Using Local Event-driven Pattern Matching   

Bilal Said and Olivier Gasquet


16.30-17.30  Local Computations in Graphs: Impact of Synchronization on Distributed Computability.

Jérémie Chalopin, University of Marseille, France

In this talk, I will present different distributed models that can be expressed by graph relabelling systems. In these models, a computation step can be described by the application of a local relabelling rule that enables the modification of the states of neighboring vertices. These models represent different level of synchronization between adjacent processes. We are interested in the computational power of these different models. In order to highlight the differences between these models, we study two classical problems in distributed computing: naming and election. The study of these problems enables to give a hierarchy between the different models and it enables to understand what kind of results are general enough to be expressed in each model.


17.30-18.30 Software demonstrations:


            Visidia: An Environment for Programming Distributed Algorithms

Mohamed Mosbah, University of Bordeaux 1

Visidia is a software tool that has been developed  in order to help in the design, the experimentation, the validation and the visualization of distributed algorithms described by relabelling systems. Visidia allows the user to model a network, to implement and to execute a relabelling system.  The tool provides a library of high level primitives to prototype, implement and visualize distributed algorithms. The user can animate the execution of a distributed algorithm without dealing with the interface programming. Visidia can be used for reach but also for teaching distributed algorithms.


            AGG: A Tool Environment for Algebraic Graph Transformation

          Gabriele Taentzer, University of  Marburg

The AGG tool environment consists of a graph transformation engine, several analysis tools for graph transformations and a graphical user interface for convenient user interaction. AGG supports the algebraic approach to typed, attributed graph transformation. It provides a typing concept for nodes and arcs which supports node type inheritance. Its attribution concept is based on Java expressions. Transformation rules may be equipped with negative application conditions. Rule applications may be controlled by graph constraints and explicit control constructs. Analysis tools offer graph parsing, critical pair analysis and applicability checks for transformation rules, as well as checking of termination criteria for controlled rule applications.