General Theory of Graph Transformation Systems
a Research Network funded by the European Community
  • Introduction
  • Research Objectives
  • Events
  • Participants
  • Vacancies --- Click here for information about the offered grants. Deadline: OPEN
  • Network Coordinator
  • Team Leaders
  • APPLIGRAPH (an ESPRIT Working Group closely related to GETGRATS)

  • Introduction

    GETGRATS (General Theory of Graph Transformation Systems) is a Research TMR Network funded by the European Commission, consisting of seven research groups that are listed here together with the corresponding team leader:
    1. University of Antwerp - UIA (Belgium): Prof. Dr. Dirk Janssens
    2. Technische Universitaet Berlin - TUB (Germany): Prof. Dr. Hartmut Ehrig
    3. Laboratoire Bordelais de Recherche en Informatique - LaBRI (France): Prof. Dr. Michel Bauderon
    4. Universitaet Bremen - UNIBREMEN (Germany): Prof. Dr. Hans-Joerg Kreowski
    5. University of Leiden - RUL (The Netherlands): Prof. Dr. Grzegorz Rozenberg
    6. Università di Pisa - UNIPISA (Italy) [main contractor]: Prof. Ugo Montanari
    7. Università di Roma La Sapienza - UNIROMA1 (Italy): Prof. Dr. Francesco Parisi Presicce
    The Network Coordinator is Andrea Corradini (Pisa). 

    Research Objectives

    The aim of the project is to develop a General Theory of Graph Transformation Systems (GTS) by solidifying the use of mathematics in their study and regarding them as the objects of discourse and interest. Particular emphasis will be placed on the comparison, combination, and unification of the various approaches to graph rewriting, where the involved partners have considerable expertise.

    The research themes to be addressed in the project are divided into the following seven "focus areas":

    Foundation, Unification, Combination and Comparison, concerning the comparison and unification of different approaches to graph rewriting, or specific aspects of such approaches.
    Classification and Expressive Power, including the identification of various structural properties of GTS that have effect on the expressive power.
    Analysis and Verification Techniques, concerning the development of analysis and verification techniques to study which properties of the semantics can be deduced or decided by inspecting the syntactic descriptions of GTS.
    Abstract Semantics, including investigation of semantics based on derivation sequences (abstract or concrete), processes and event structures, especially in the light of research about modularity and concurrency.
    Concurrency Aspects, concerning the development of concepts of concurrent and distributed GTS including appropriate semantics, as well as their comparison to other models for concurrency.
    Modularity Aspects, including the definition of module concepts, borrowing techniques from other areas like abstract data types.
    Morphisms, Transformations and Operations, including the definition of suitable categories of graph processes, event structures and other abstract domains, and to relate them with categories of grammars through functors, or, better, through adjunctions.



    The following table summarizes the participation of the partners to the various focus areas; moreover, it shows for each focus area which partner will coordinate the activities within that area (indicated by "[x]").
                 |           | a | b | c | d | e | f | g |
                 |UIA        |   |   |   |[x]| x | x |   |
                 |TUB        | x |   | x | x |[x]| x | x |
                 |LaBRI      |[x]| x | x |   | x |   |   |
                 |UNIBREMEN  | x | x |[x]|   |   | x |   |
                 |RUL        | x |[x]| x |   | x | x |   |
                 |UNIPISA    |   |   | x | x | x | x |[x]|
                 |UNIROMA1   | x |   |   | x | x |[x]| x |
    In the research activity of the project various "formal frameworks", that is, mathematical disciplines, will be used. In particular, the following five formal frameworks will be considered: Formal Language Theory, Graph Theory, Algebra and Universal Algebra, Logic, and Category Theory.

    A more detailed description of the Research Objectives of GETGRATS is available in postscript and dvi.


    During the GETGRATS project the following main scientific events will be (or have been) organized: The two Workshops are the major events where the progress of the joint research among the partners is presented and discussed. The European School will include basic courses on Graph Transformation Systems, presented by members of the project or by external specialists, and it will have the goal of attracting young students and researchers from outside the area.

    Furthermore, for each of the Focus Areas listed above, a Meeting of more technical nature will be organized, including both presentations of the work in progress and joint planning and working sessions. If you are interested to receive timely information about the planning of the Focus Area Meetings, ask the coordinator to subscribe the GETGRATS mailing list.


    University of Antwerp - UIA (Local GETGRATS page)

    PRINCIPAL RESEARCHERS: Dirk Janssens (team leader), Nico Verlinden, Juergen Mueller, Ingrid Fisher (Univ. of Erlangen), Jan Van den Bussche (Limburgs Universitair Centrum), Jan Paredaens, and Marc Gemis.

    The expertise of UIA covers a number of theoretical aspects as well as application areas. The group has experience concerning the language theoretic aspects of node-based graph rewriting systems, their use as models of computation, and the use of graph transformations in databases. Janssens has made a substantial contribution to the investigation of node-rewriting systems and their languages. More recently he contributed to the development of graph-rewriting models for concurrent and object-oriented computation. This includes the investigation of the models as such (concurrent semantics, modularity, etc.) as well as their relationship to other models (such as Petri nets and pi-calculus), and the study of possible applications (e.g. to protocol verification and design). In cooperation with I. Fisher the use of GTS as semantic model for Actor Systems has been investigated. Paredaens and Van den Bussche are experts in the area of models and languages for databases. They have investigated the potential of GTS as a conceptual tool for object oriented databases; in particular from the viewpoint of expressiveness and complexity of data manipulation languages. Gemis has experience in the use of such GTS tool for the implementation of object oriented databases. The expertise of UIA enables it to contribute to the development of GTS as an important conceptual tool for expressing ideas about the semantics of programming languages.

    TRAINING ACTIVITY: The department offers curricula in computing science at the masters (4 year) and ph. D. level. Recent results in Graph Transformation systems have been presented in a research seminar aimed at young researchers. The various members of the staff working on GTS or closely related subjects have supervised and encouraged work by young researchers at various levels, leading to a number of research papers, and theses (masters and Ph.D.).

    Technische Universitaet Berlin - TUB

    PRINCIPAL RESEARCHERS: Hartmut Ehrig (team leader), Gabriele Taentzer, Julia Padberg, Reiko Heckel, Magdalena Gajewski, Roswitha Bardohl, Fabio Gadducci, and Manuel Koch
    COOPERATE RESEARCHERS: Martin Korff, Leila Ribeiro (URFGS Porto Allegre, Brazil), Alfio Martini, Hans-Juergen Schneider (Universitat Erlangen, Germany), and Gabriel Valiente (Universidad Politecnica de Catalunya, Spain).

    The algebraic approach to graph transformation has been created in the early seventies at TU Berlin. Since then it became one of the most successful approaches, providing a rich theory for the modeling of concurrent and distributed systems, their structuring and analysis.

    The TUB group has been coordinator of the ESPRIT projects COMPUGRAPH "Computing by Graph Transformation" I and II, and member within several national and international projects on formal specification methods as, for example, COMPASS on algebraic specification. Current research projects include the german DFG project "Structuring and Analysis of Algebraic Graph Transformation Systems", the DFG research group project "Petri Net Technology", the ESPRESS project on specification of safety-critical systems using Statecharts and Z, and the cooperation project GRAPHIT with Brazil on integration of formal and informal (graphical) specification techniques.

    Major topics of current research, beside graph transformations, are algebraic specifications, high-level Petri nets, and the comparison and integration of different specification techniques. In the area of graph transformations current research activities include structuring, analysis, and semantics, and the application of graph transformation techniques for the specification of parallel and distributed systems. Within GETGRATS the TUB group will contribute to the focus areas Foundation, Unification, Combination and Comparison; Analysis and Verification Techniques; Abstract Semantics; Concurrency Aspects; Modularity Aspects; and Morphisms, Transformations and Operations.

    TRAINING ACTIVITY: At TUB several courses are given where graph transformation is treated in different ways. In a basic course called "Rewriting systems" algebraic graph transformation is introduced as one rewriting formalism (among others). This knowledge can be further extended in both the theoretical side and the practical direction, where the students have to specify a software system by graph transformation. Weekly a meeting takes place where all people concerned with graph transformation come together, present their publications, talk about recent ideas and discuss problems. Moreover, TUB offers a Ph.D. program in computer science on communication-based systems. Within this program several seminars have taken place where graph transformation have been applied as specification method for communication-based systems.

    Laboratoire Bordelais de Recherche en Informatique - LaBRI

    PRINCIPAL RESEARCHERS: Michel Bauderon (team leader), Bruno Courcelle, Yves Métivier, Géeraud Séenizergues, Robert Strandh, Iréene Durand, Mohamed Mosbah, Nasser Saheb, Pierre-Andrée Wacrenier and 9 Ph.D. students.

    The LaBRI (Laboratoire Bordelais de Recherche en Informatique) which gathers more than one hundred researchers from various schools and universities in Bordeaux is considered as one of the best laboratories in France for computer science (especially theoretical computer science). Since 1989 LaBRI has participated to the ESPRIT Working groups COMPUGRAPH I and II, and ASMICS and has developed (often pioneered) research on the following topics: use of Universal Algebra to handle context-free graph grammars of all types and infinite equational graphs (Bauderon, Courcelle); use of monadic second-order logic to describe graph properties and graph transformations, and to obtain efficient algorithms from them such as a good test for minors; incremental algorithms on graphs with bounded tree-width (Courcelle); properties of graphs in the plane, maps, axiomatisation of alignments, placements of graphs with visibility description of distributed graph algorithms in terms of graph relabelling systems (Méetivier) as a tool to prove properties like correctness, (local or global) termination, confluence, ...; use of products and pullbacks in suitable categories of graphs to provide a uniform description of graph rewriting (Bauderon); use of rewriting systems as programming languages, with special interest to efficient compilation of rewriting systems through a technique of specialisation of programs (Strandh).

    TRAINING ACTIVITY: Besides classical engineering and Master programs in both practical and theoretical computer science, LaBRI is offering Ph.D. programs in various areas of Computer Science, be they theoretical (Combinatorics, Graph Theory, Graph Rewriting, Transition Systems, ...) or practical (Image Processing and Synthesis, Parallel Computing, Networks and Protocols, ...). Several weekly seminars present recent works in those fields. Moreover, LaBRI is regularly organising "Young Researchers Schools", which on a specific topic gather 30 to 40 researchers from various laboratories in France.

    Universitaet Bremen - UNIBREMEN (Local GETGRATS page)

    PRINCIPAL RESEARCHERS: Hans-Joerg Kreowski (team leader), Frank Drewes, Renate Klempien-Hinrichs, Peter Knirsch, Sabine Kuske, Detlef Plump, and Annegret Habel (Universitaet Hildesheim).

    The expertise of the UNIBREMEN team concerns mainly the foundational and theoretical aspects of graph transformation with additional interest in potential applications.

    The main areas of research are

    The UNIBREMEN team runs a Theoretical Computer Science seminar where research ideas and results are presented and discussed. The seminar is open to everyone who wants to present his or her results or simply wants to listen to the presentations given. In principle, the whole area of Theoretical Computer Science is covered, but usually the topics are somehow related to the field of graph transformation.

    University of Leiden - RUL

    PRINCIPAL RESEARCHERS: G. Rozenberg (team leader), J. Engelfriet, H.-J. Hoogeboom, G. Engels (University of Paderborn, Germany), T. Harju (University of Turku, Finland), A. Schuerr (University of Aachen, Germany)

    The expertise of the RUL group stretches from theoretical to applied aspects of graph transformations.
    Rozenberg, Engelfriet and Hoogeboom have the knowledge and experience in the language-theoretic, graph-theoretic, algebraic and logical aspects of graph transformations, in particular concerning 2-structures and context-free graph grammars.
    Engels and Schuerr have the knowledge and experience in applying graph transformations systems in software engineering, both on the conceptual level as on the implementation level. In particular this group has considerable experience in research on parsing, semantics, concurrency, modularity, and transformation aspects of graph transformation systems.

    TRAINING ACTIVITY: RUL runs two research seminars, where also the results on graph transformation systems are reported. Also, currently there are three lectures ("Parsing of Visual Languages", "2-Structures", "Recursive Grammars"), where different aspects of graph transformation systems are discussed. The institute in Leiden offers a stimulating research environment for young researchers, where they can discuss research problems among themselves and with the faculty involved in research on graph transformation systems.

    Università of Pisa - UNIPISA

    PRINCIPAL RESEARCHERS: U. Montanari (team leader), A. Maggiolo Schettini, A. Corradini (network coordinator), P. Baldan and F. Rossi (Univ. of Padova).

    The Dipartimento di Informatica of the University of Pisa was the first established Italian department of Computer Science. It has a faculty of about 40 people, covering most main areas in computer science research, including Algorithms and Data Structures, Parallel and Distributed Architectures, Artifical Intelligence and Robotics, Database and Information Retrieval, Computational Mathematics, Operating Research, Programming Languages, and Software Engineering.

    The Models of Computation & Concurrency Group at the Department of Computer Science in Pisa has more than a decade of history of active research in the field of (concurrent) models of computations for process algebras, Petri nets, lambda-calculus, term and graph rewriting systems, shared and distributed memory systems. The group also contributed to the development of tools for protocol verification. Graph Transition Systems have been actively studied especially for what concerns their concurrent aspects. GTS have been employed to provide a truly concurrent semantics of other formalisms, like mobile functional languages (pi-calculus) and concurrent constraint languages.

    TRAINING: The Dipartimento di Informatica offers computing curricula both at the Diploma (3 years), Laurea (5 years) and at the Ph.D. level (this year 13 courses for the Ph.D. curriculum are offered). It had a pioneering role in Italy in organizing computing curricula.

    Università di Roma La Sapienza - UNIROMA1

    PRINCIPAL RESEARCHERS: F. Parisi Presicce (team leader), S. Levialdi, P. Bottoni, M. Simeoni and A. Pierantonio (University of L'Aquila)

    The Research Group in Roma consists of members with a history of active research in the field of models computations, algebraic specification of software systems, term and graph rewriting systems, formalization of visual languages. Different members of the group have participated (before and after joining the University of Roma La Sapienza) in various national and international projects including Esprit Working Groups and HCM networks.

    The Dipartimento di Scienze dell'Informazione of the University of Roma La Sapienza was established in 1991. It offers computing curricula both at the Diploma (3 years), Laurea (5 years) and Ph.D.level. It has a faculty of about 20 people whose research interests include Algorithms and Graph Theory, Complexity Theory, Functional and Logic Programming, Parallel Algorithms and Architectures, Pictorial Computing, and Formal Methods for System Design.

    Network Coordinator

    Dr. Andrea Corradini

    Dipartimento di Informatica
    Corso Italia 40
    56125 Pisa, ITALY

    tel: +39 050 887266
    fax: +39 050 887226

    Team Leaders

    Prof. Dr. Dirk Janssens

    Department of Mathematics and Computer Science
    Universiteitsplein 1
    B-2610 Antwerpen, BELGIUM

    tel: +32 3 8202405
    fax: +32 3 8202421

    Prof. Dr. Hartmut Ehrig

    Institut fuer Kommunikations- und Softwaretechnik
    Technische Universitaet Berlin
    Sekr. FR 6-1
    Franklinstrasse 28/29
    D-10587 Berlin, GERMANY

    tel: +49 30 31473511/510
    fax: +49 30 31423516

    Prof. Dr. Michel Bauderon

    Laboratoire Bordelais de Recherche en Informatique (LaBRI)
    Universite' Bordeaux I
    351, Cours de la Liberation
    F-33405 Talence Cedex, FRANCE

    tel: +33 556 84 69 07 or +33 556 84 58 24
    fax: +33 556 84 66 69 or +33 556 84 79 09

    Prof. Dr. H.-J. Kreowski

    Fachbereich Mathematik/Informatik
    Universität Bremen
    Postfach 330440
    D-28334 Bremen, GERMANY

    tel: +49 421 2182956
    fax: +49 421 2184322

    Prof. Grzegorz Rozenberg

    Dept. of Computer Science
    University of Leiden
    Niels Bohr weg 1
    P.O. Box 9512
    2333 CA Leiden, THE NETHERLANDS

    tel: +31 71 5277067
    fax: +31 71 5276985

    Prof. Ugo Montanari

    Dipartimento di Informatica
    Corso Italia 40
    56125 Pisa, ITALY

    tel: +39 050 887221
    fax: +39 050 887226

    Prof. Dr. Francesco Parisi Presicce

    Dipartimento di Scienze dell'Informazione
    Via Salaria 113
    I-00198 Roma, ITALY

    tel: +39 06 49918361
    fax: +39 06 8841964

    Andrea Corradini (