September 9 – 13 , 1996, Dagstuhl Seminar 9637

Graph Transformations in Computer Science


H. Ehrig, U. Montanari, G. Rozenberg, H.J. Schneider

For support, please contact

Dagstuhl Service Team


Dagstuhl's Impact: Documents available
Dagstuhl-Seminar-Report 155


The research area of graph transformations dates back to the early seventies. Its methods, techniques, and results have already been applied in many fields of computer science such as formal language theory, pattern recognition and generation, compiler construction, software engineering, concurrent and distributed systems modelling, database design and theory, and so on. This wide applicability is due to the fact that graphs are a very natural way to explain complex situations on an intuitive level. Graph transformation brings dynamics to all these descriptions and can describe the evolution of structures. Therefore graph transformation has become attractive as a programming and specification paradigm for complex structured software and graphical interfaces. In particular graph rewriting is promising as a comprehensive framework in which the transformation of all these very different structures can be modelled and studied in a uniform way. The operational approach immediately formalizes a specific type of graph transformation and may be implemented efficiently. On the other hand, the categorical approach yields attractive formal properties. In recent years this approach was extended to high-level replacement systems and was modified by replacing the double-pushout construction both by a single-pushout construction and by a pullback construction. The evolution of the field and the state-of-the-art are documented in six volumes of Lecture Notes in Computer Science (73, 153, 291, 532, 776, and 1073).

During this Dagstuhl-Seminar, 35 lectures were presented by the participants from seven European countries, Brazil, Israel, and Japan on foundations as well as on applications. Comparing the abstracts in this booklet with those of the previous Dagstuhl-Seminar on this topic (Report No. 53), we observe a clear shift to the new aspects of foundations mentioned above and to specification of concurrent and distributed systems. System demonstrations showed the improvement of efficient implementations and let us expect that the gap between formal methods in system development and graphical methods can be bridged over by graph-transformation based methods.

Altogether the seminar led to fruitful discussions between theory and application and between advocates of different approaches. The participants appreciated the stimulating atmosphere in Schloß Dagstuhl.

Finally, I would like to express my warmest thanks to the co-organizers; unfortunately two of them, Hartmut Ehrig and Grzegorz Rozenberg, could not attend the seminar because of sickness; nevertheless, they also have contributed to the success of the seminar by their co-operation in preparing it.

Related Dagstuhl Seminar


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.