TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 9301

Graph-Transformations in Computer Science

( 04. Jan – 08. Jan, 1993 )

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/9301

Organisatoren
  • B. Courcelle
  • G. Rozenberg
  • H. Ehrig
  • H.J. Schneider




Summary

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.


Teilnehmer
  • B. Courcelle
  • G. Rozenberg
  • H. Ehrig
  • H.J. Schneider

Verwandte Seminare
  • Dagstuhl-Seminar 9637: Graph Transformations in Computer Science (1996-09-09 - 1996-09-13) (Details)