The research area of graph grammars resp. graph transformations is a relatively young discipline of computer science. Its origins date back to the early seventies. Nevertheless methods, techniques, and results from the area of graph transformation have already been studied and 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, etc.

This wide applicability is due to the fact that graphs are a very natural way to explain complex situations on an intuitive level. Hence they are used in computer science almost everywhere, e.g. as data- and control ow diagrams, entity relationship diagrams, Petri-nets, visualization of soft- and hardware architectures, evolution diagrams of non-deterministic processes, SADT-diagrams, and many more. Like the "token game" for Petri-nets, graph transformation brings dynamics to all these descriptions, since it can describe the evolution of graphical structures. Therefore graph transformation becomes attractive as a "programming 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.

During this Dagstuhl-Seminar 33 lectures and 3 system demonstrations weere presented by the participants from 8 European countries, U.S.A. and Japan in the following areas:

• Foundations of Graph Grammars and Transformations
• Applications of Graph Transformations to
• Concurrent Computing
• Specification and Programming
• Pattern Generation and Recognition

The system demonstrations in the evening showed efficient implementations of the algebraic approach to graph transformations (AGG-System), of a software specification language based on graph rewriting (PROGRESS) and of a functional programming language (Concurrent Clean) based on term graph rewriting. In each case the theoretical techniques of the underlying approach and typical applications have been demonstrated in corresponding lectures during the day. In addition, interesting new applications of graph transformations were presented in several lectures in the following areas: Concurrent constraint programming, actor systems, specification of languages for distributed systems, of hybrid database languages and of an efficient narrowing machine, and -last but not least- to pretty pattern generation and recognition ranging from graphical modelling for CAD to abstractions of modern art including Escher and Picasso.

In the lectures concerning foundations on one hand new results concerning graph languages and graph automata and their connections to decision problems were presented. On the other hand new concepts and results for the algebraic approach to graph transformations based on double and single pushouts were shown. Notions for abstraction and semantical constructions were given leading to canonical derivation sequences, true concurrency and event structures and also extensions of results from graph grammars to HLR (High Level Replacement)-systems. The HLR-approach is a categorical unification of different approaches with several interesting new applications including those to rule based modular system design and transformation and refinement of Petri-nets.

Altogether it was a very fruitful interaction between theory, applications and practical demonstrations.

This Dagstuhl workshop was coorganized by the ESPRIT Basic Research WG COMPUGRAPH and will be followed by a series of related workshops in Leiden (Fall 1993), Williamsburg, U.S.A. (1994), Pisa (1995) and hopefully again in Dagstuhl in 1996. A All participants appreciated the stimulating atmosphere in Schloß Dagstuhl and expressed their thanks to the IBFI (Internationales Begegnungs- und Forschungszentrum für Informatik) and the ESPRIT WG COMPUGRAPH for organization and support of this successful seminar.