Computing by Graph Transformation


Work Area: Logics and Logic Programming

Keywords graph transformations, concurrent computing, operational semantics

Start Date: 1 October 92 / Duration: 36 months / Status: running

[ participants / contact ]

Abstract COMPUGRAPH II is working towards a unification and extension of the theory of graph transformation so that it can provide a uniform paradigm for computing, that is, for the specification, implementation, programming, and analysis of sequential, parallel and distributed systems. The Group continues the work of COMPUGRAPH I (3299).


The major aim of COMPUGRAPH II is to demonstrate the potential of graph transformation as a uniform framework for the development of modern software systems. In order to reach this aim, objectives have been established under the headings of foundations, concurrent computing, and graph transformation for specification and programming.

Within the area of foundations, research is directed towards the unification, extension, and completion of existing graph transformation theories.

In concurrent computing, the aim is to elaborate a graph transformation-based approach which can provide operation semantics for various models of concurrent computing (including Petri-nets and process description languages) and enhances correct and comprehensive specifications.

The graph transformation for specification and programming area considers graph transformation as the kernel of a rule-based specification language and aims at extending this kernel by typing mechanism, module and transformation concepts, applicability constraints, transactions, and concepts developed within concurrent computing in order to improve the feasibility of graph rewriting as a system specification method.


The work within COMPUGRAPH II is structured around three research areas: foundations; concurrent computing; graph transformation for specification and programming. Smaller teams have been established to tackle area-based issues.

This work will be organised by joint research and several meetings of two or more partners in each team in cooperation with European and international experts; for this reason the Group has drawn up an non-exclusive list of 11 scientific correspondents.

Three international workshops - including one in the USA in 1994 (for which an additional joint ESPRIT/NSF proposal has just been accepted) - will be used to demonstrate and integrate the results of the research areas. Moreover results will also be presented in scientific journals and at European and international conferences. COMPUGRAPH II will participate in and contribute to workshops of ESPRIT groups investigating related issues, including SEMAGRAPH II (6345), COMPASS II (6112), and workshops and conferences in the area of theoretical and applied Computer Science.

Progress and Results

Among the number of new results and developments we mention the following:

A "Hybrid Query Language" for extended entity relationship databases has been developed. The language integrates graphical and textual notations. Its semantics is based on graph transformations.

There is an ongoing research of applying High-Level Replacement-Systems to different kinds of Petri-Nets. This has already lead to important new results for net transformation systems with interesting applications to specification of distributed systems.

A suitable variant of graph-grammars has been used to specify the operational behaviour of an abstract machine that implements narrowing. Various graph grammars are used to specify the behavior of the machine at different levels of abstraction: the various levels are related by formal results, stating the soundness and correctness of the implementation of each level in terms of the lower one.

The notion of an actor grammar has been generalised to the more natural notion of an ESM system for which a compositional semantics has been presented. A different graph transformation model of actor systems has motivated the investigation of transformations dealing with consistent graph structures only.

A new framework for attributed graph transformations has been proposed. The manipulation of values taken from a suitably specified algebra is smoothly integrated into the framework of single pushout graph transformations.

Investigations about a new, truly-concurrent semantics for graph-grammars (in the double-pushout approach) has been started. The first relevant result is the definition of an original notion of equivalence among graph derivations, which relates derivations which are essentially the same from the truly-concurrent point of view. This is the first step towards the definition of an event structure semantics for graph grammars.

"Collage grammars" have been introduced as a rule based device for picture generation. Collages consist of geometric objects together with entities ("hyperedges") that are repeatedly replaced by collages during the generation process. The pictures that can be produced by collage grammars include certain fractal patterns.


COMPUGRAPH II should provide a solid semantic foundation for new system specification and programming paradigms based on unified graph transformation models and the necessary theoretical background for initiating languageand CASE-based projects centered around these paradigms.

Latest Publications

Information Dissemination Activies

Three international workshops have already been organised by the COMPUGRAPH community:

In addition to the workshops above, in 1993 papers have been contributed to the following conferences: LICS '93, RTA '93, ICALP '93, FCT '93, Tapsoft '93, and AMAST '93.

There will further be an international COMPUGRAPH workshop in Leiden, Netherlands, in October '93, and moreover, a joint ESPRIT/NSF workshop "5th International Workshop on Graph Grammars and Their Application to Computer Science", in Williamsburg, USA, in November 1994.


Technische Universität Berlin - D
Fachbereich Informatik
Franklinstrasse 28/29
D - 10587 Berlin


Vrije Universiteit Brussel - B
Universität Bremen - D
Université de Bordeaux I - F
Università di Pisa - I
Rijksuniversiteit Leiden - NL


Prof. Dr. H. Ehring
tel +49/30 31473510
fax +49/30 31423516

LTR synopses home page LTR work area index LTR acronym index LTR number index LTR Working Groups index
All synopses home page all acronyms index all numbers index

COMPUGRAPH II - 7183, August 1994

please address enquiries to the ESPRIT Information Desk

html version of synopsis by Nick Cook