Graphs are widely used to represent complex states, structured objects, networks, and relations among components. Even wider, rules are used to define permitted actions and transitions. Together, graphs and rules yield the promising paradigm of graph transformation, which provides a rich methodology for modelling information processing systems (including distributed systems) and for analysing their behaviour. The theory of graph transformation has made tremendous progress in the last decade-in particular due to the achievements of the ESPRIT Basic Research Action and Working Groups nos. 3074, 6345, 3299, and 7183 (SEMAGRAPH I and II (Semantics and Pragmatics of Generalised Graph Rewriting), July 1989 - June 1992 and October 1992 - September 1995, and COMPUGRAPH I and II (Computing by Graph Transformation), March 1989 - August 1992 and October 1992 - March 1996).
Based on the well-developed foundations, the time seems ripe now to intensify the research on applications of graph transformation and to work out its technological potentials. The aims of this Working Group are
Language issues. Investigation of features in graph transformation based languages, like typing, modularity, refinement, parallelism, concurrency, distribution, optimisation, and correctness.
Tool issues. Conception and design of support tools for graph transformation based languages including editors, parsers, interpreters, compilers, optimisers, verifiers, and graphical user interfaces.
Application domains. Demonstration of the usefulness of graph
transformation by
case studies in various areas like definition of visual languages,
database models,
concurrent and distributed systems, software process modelling,
implementation of programming languages.
Among the main activities, the Working Group will organise workshops and meetings and will disseminate information on applied graph transformation by publishing proceedings and handbooks. The goal is to enhance the visibility of graph transformation technology and to prepare the ground for industrial applications.
Graph transformation links two quite successful concepts: graphs and rules. Graphs are well-known, well-understood, and frequently used means to represent system states, complex objects, diagrams, and networks of various kinds like flowcharts, entity-relationship diagrams, Petri nets, and many more. Rules have proved for a very long time to be extremely useful wherever permitted actions and transitions must be described. Areas like language definition, logic and functional programming, algebraic specification, term rewriting, theorem proving, concurrent processes, expert systems, and others witness the prominent role of rules. The framework of graph transformation combines the potentials and advantages of both, graphs and rules, into a single computational paradigm.
The variety of approaches, the major scientific achievements as well as some working applications are fairly well documented and surveyed in the literature (see, e.g., [CER79,CM95,ENR83,ENRR87,EKR91,Ha92,SE94,PvE93,SPE93]). The significant progress the area of graph transformation has made in the last decade is mainly owed to the activities within the ESPRIT Basic Research Action and Working Groups SEMAGRAPH I and II and COMPUGRAPH I and II.
APPLIGRAPH will rely on the well-developed theory of graph transformation and will carry on the experiences of COMPUGRAPH and SEMAGRAPH. It is intended to be an initiative towards intensified research on applications of graph transformation, the demonstration of its usefulness in selected application domains, and the improvement of the awareness of its industrial relevance and technological potentials. In order to achieve the aims, three lines of research will be pursued: language issues, tool issues, and application domains. The main effort must be laid on making the potentials of graph transformation more visible in application domains by illustrating case studies. In order to provide the necessary support and background, language issues and tool issues need further attention.
1. Language issues.
Graph transformation as a rule-based framework
yields a new type of specification and programming languages, ranging from
rather specific ones for small application domains to more general-purpose
languages. The following topics must be addressed in particular.
1.1 Modularity
It is widely accepted that modularity, together with corresponding techniques
for encapsulation and abstraction, is a key issue in any attempt to support
the software development process. In order to develop large specifications and
programs in a language based on graph transformation, one needs abstraction
concepts, structuring principles and control mechanisms.
1.2 Parallelism and concurrency
The Working Group aims at coordinating the development of a language in which
the communication between concurrently active system components can be more
easily described and controlled. This is based on the generalisation of
notions developed for Petri nets, such as processes and true concurrency
semantics, to graph transformation and can be considered as a step towards a
wider applicability of Petri nets.
1.3 Optimisation and correctness
On the one hand, graphs have a mathematically well-understood logic theory,
and rule-basedness of graph transformation on the other hand leads to
induction principles. Both together provide a powerful framework for
correctness proofs, semantic analysis, and optimisations including consistency
checking and symbolic reduction.
1.4 Language design
The key issue in this area is the direct use of graph transformation as a new
type of specification and programming language. Since data structures can
often be viewed as graphs, such languages provide comfortable and intuitive
means to develop reliable software. This is demonstrated by the promising
experiences with the language PROGRES (Aachen) and CONCURRENT CLEAN (Nijmegen), suggesting an intensification of this line of research.
2. Tool issues.
Support tools for graph transformation based languages
will be designed and used to produce specifications of applications, to
analyse them, and to animate and prototype applications. The development of
tools will give necessary feedback about the usefulness and the efficiency of
developed languages.
2.1 Editors, analysers, and parsers
For a rather long time graph transformation users had
to write, check, and animate their specifications by hand. Nowadays
the situation is gradually improving with the appearance of
graph transformation environments that offer valuable support
for editing graphs and graph transformation rules via a visual
interface. It is time now, to exchange the experiences
of different research groups, to identify reusable components, and to
distribute knowledge
about existing developments.
2.2 Interpreters, compilers, and optimisers
Interpreters for languages based on graph transformation allow to inspect
the reduction process in an interactive
way. This can be of great help in program construction.
The drawback of interpreters is their inefficiency.
Therefore, the execution of real-world applications require a state-of-the-art
compiler in addition. Here, optimisation techniques play an important
role.
2.3 Graphical user interfaces
Due to the natural visual representation of graphs, their transformation
corresponds to the animation of visual objects. This is the key idea of
combining graph transformation tools with a graphical interface and of
visualising and animating graphs, rules, and transformations at various levels
of abstraction.
2.4 Generating and prototyping tools
End users of a specified language or system must not be forced to read and
understand the specification of the underlying graph transformation system.
They need the opportunity to test a generated prototype while the user
interface hides any specification details. It may even abstract from the
underlying graph data model using a variety of different user interface
metaphors.
3. Application domains.
The usefulness of graph transformation will be
demonstrated by case studies in various areas, making the technological
potential of the paradigm more visible. The specification of applications will
give necessary feedback for the refinement and development of languages and
concepts, and the application of tools will give feedback about the
appropriateness of their interfaces, functionality, etc. and of their
underlying languages.
3.1 Visual languages
Graph-based specification languages have been used successfully as
an easy-to-use and well-formalised paradigm to specify the syntax of
visual languages (Aachen, Leiden), and this approach towards visual
syntax definition might very well become the ``BNF'' of visual
language research. This requires powerful
graph parsing algorithms, tools which support the definition of
visual syntax, and syntax-directed graphical
editors.
3.2 Database models and information systems
Visual database languages and systems are becoming more and more important.
As demonstrated by the work on the GOOD model (Antwerp), graph
transformation is adequate for the description of general purpose Object
Oriented Databases and graph manipulations are easier to understand than
textual ones. Now, the use of graph transformation for more specialised types
of databases has to be investigated.
3.3 Concurrent and distributed systems
Petri nets and their high-level variants are widely accepted as a
specification formalism for concurrent and distributed systems. They enjoy an
elegant, well-understood semantics expressing concurrency in a direct way.
Graph transformation smoothly generalises most pleasant properties of nets and
overcomes some of the deficiencies of Petri nets, like the restricted state
representation and the lack of dynamic system changes. Therefore graph
transformation systems look very promising for the specification of
distributed systems whose topologies are changing in time.
3.4 Computer-supported cooperative work and distributed business process re-engineering
Computer Supported Cooperative Work (CSCW) is an active field of research,
addressing the problem of modelling the dynamic features of cooperative work.
Similarly, Distributed Business Process Re-engineering (DBPR),
is concerned with the challenging task of restructuring enterprises and work
processes. Graph transformation systems provide a non-ambiguous and consistent
representation of networks of cooperating agents which can be used to cover
all the dynamic aspects of such models, still maintaining a clear semantics.
The use of graph transformation in DBPR as planned for the projects
KORPUS and MOKASSIN (Bremen) allows for the first time
the adequate handling of distributed and parallel business processes.
3.5 Design and implementation of programming languages
Graph transformation provides a powerful model to design and implement
programming languages for applications that demand parallel and distributed
evaluation. This is convincingly demonstrated by the language Concurrent Clean
(Nijmegen). A central aim must be to test the suitability of such programming
languages for writing real-world applications.
3.6 Specification of software engineering models
The GRIDS project (Leiden) provides a formally based,
multi-dimensional
software engineering model and tool that integrates ``partial''
models of software processes, system architectures, and views onto the
system, to enhance
real-life, large-scale software development. It has been described
using the programmed graph rewriting system
PROGRES (Aachen) and provides the basis for further developments in
this direction.
Projects with industrial partners or sponsors. GRIDS, with TNO Institute of Applied Geoscience, 1992-1996 (Leiden, cf. 3.6), IRIS (image retrieval application, supported by IBM (Bremen), KORPUS with Mercedes-Benz AG and DASA, supported by the government of Bremen; begin 1996) (Bremen, cf. 3.4), and MOKASSIN with MTW shipyard Inc., Bremer Vulkan Verbund AG, and PS Systemtechnik Inc., supported by the German Federal Ministry for Research and Technology; begin 1996) (Bremen, cf. 3.4)
European research projects. ESPRIT BR Actions ACCLAIM (no. 7195, Advanced Concurrent Constraint Languages: Application, Implementation and Methodology [Pisa]), CONFER (no. 6454, Concurrency and Functions: Evaluation and Reduction [Pisa]), and Parallel Computing (Nijmegen),ESPRIT BR Working Groups ASMICS (no. 6317, Algebraic and Syntactic Methods in Computer Science [Berlin]), CALIBAN (no. 6067, Casual Calculi Based on Nets [Leiden]), COMPUGRAPH II (no. 7183, Computing by Graph Transformation [Antwerp, Berlin, Bremen, Leiden, Pisa]), PROMOTER (no. 7082, Process Modeling Techniques: Basic Research [Leiden]), SEMAGRAPH II (no. 6345, Semantics and Pragmatics of Generalised Graph Rewriting [Nijmegen]), and COMPASS II (no. 6112, A Comprehensive Approach to Program Development and System Specification [Bremen, Berlin, Rome]), ESPRIT Tropics project (Tip-m 2427 [Nijmegen]), and ESPRIT IV proposal COMPASS III (A Comprehensive Approach to Program Development and System Specification [Bremen, Berlin, Rome]).
National research projects. Graduiertenkollegs Communication Based Systems (DFG no. GRK 86/2-96 [Berlin]) and Informatics and Technology (DFG no. Sp 230/6-7 [Aachen]), DFG-Forschergruppe SUKITS, Software and Communication Structures in Technical Systems (no. Na 134/5-2 [Aachen]), Performance and Reliability of Object-Oriented Systems (NFWO no. GO 22296 [Antwerp]), DFG projects Structuring and Analysis of Algebraic Graph Transformation Systems (no. Eh65/7-1 [Berlin]) and Collage Grammars (no. Kr 964/4-2 [Bremen]), and proposal for DFG project Theoretical Foundations of the Redevelopment of Software Systems (Based on Graph Transformations) [Berlin].
Moreover, 8 of the 12 key members of the proposed Working Group participate in the TMR research network proposal GETGRATS (General Theory of Graph Transformation Systems) coordinated by Ugo Montanari. It emphasises foundational and training aspects of graph transformation and will therefore be an ideal complement of APPLIGRAPH.
APPLIGRAPH should be seen in succession of the two ESPRIT Basic Research Working Groups COMPUGRAPH I and II. It will extend and strengthen the applied side of COMPUGRAPH rather than just continue activities. This is witnessed, for example, by the change in the consortium with several new members (Herzog, Nagl, Paredaens, Plasmeijer, Weber) from practical and applied computer science.
Applied computer science and industry becomes more and more aware that the dynamics in modern information and communication infrastructures cannot be controlled without an underlying unifying paradigm for the engineering and, even more important in the future, re-engineering of systems.
If the known advantages of graph transformation can be integrated into these techniques for system engineering, major progress can be expected with respect to reliability, controllability, compactness, and uniformity of description, and easier understanding and changing of industrial software systems. The focus of the APPLIGRAPH project on languages, tools, and application-oriented case studies ensures that a big step in this direction will be done.
Workshops and symposium. For the first year an APPLIGRAPH Workshop is planned assembling the members and scientific correspondents and further experts of the field. In 1997, the 6th International Workshop on Graph Grammars and their Application to Computer Science will be (co-)organised by members of the Working Group. In the third year, an APPLIGRAPH Symposium on Perspectives and Industrial Relevance of Graph Transformation will be organised to bring together researchers in the field with interested people from industry, and in particular from software industry.
Business meetings. Adjoint to each of the three major events, there will be a business meeting of the members of the Working Group for organisational purposes. It is also intended to have extra team leader meetings, if necessary, for the planning and coordination of Working Group activities.
Subgroup meetings. In addition to the three major events, subgroup meetings will be held on particular research topics two or three times a year. Each subgroup meeting will have about 10 participants and will be organised by one of the Working Group teams either as a separate event or joint to a European conference. Up to now, the following topics for subgroup meetings are envisaged:
Continuing regular research. Clearly, the members of the Working Group will continue to carry out research on topics of interest in graph transformation as described above, and they are expected to present their work at major international conferences. In addition, the Working Group will make efforts in information dissemination as is detailed below.
A handbook on Foundations of Graph Transformation, edited by G. Rozenberg, will soon appear with World Scientific Publishers. The Working Group plans to publish two further handbooks on applied graph transformation (one volume on Specification and Programming by Graph Transformation, the other on Parallelism and Concurrency in Graph Transformation) both together covering the topics of APPLIGRAPH. In addition, the Working Group will support the editing of the proceedings of the 6th International Workshop on Graph Grammars and their Application in Computer Science that are regularly published in the Springer LNCS series.
The Working Group will run a WWW site to inform about its achievements and activities and to provide access to finished papers. For the mutual and fast exchange of information among the members of the Working Group and interested people from outside, an electronic bulletin board will be installed. The idea is to use internet facilities as a permanent newsletter. The information collected in this way will be put together into an annual progress report.
Working group coordinator: Hans-Jörg Kreowski
Working group manager: Detlef Plump
Area coordinators:
Event organisers:
The Working Group coordinator is responsible for the organisational and administrative management of the Working Group. He acts as the principal contact person with the Commission and ensures that the progress reports are worked out and delivered to the Commission in time. Together with the Bremen team he manages the WWW site of the Working Group and the electronic bulletin board. In these tasks he is supported by the manager.
Each area coordinator supports the Working Group coordinator and coordinates the work within the respective area. He ensures that the contributions to the reports reach the Working Group coordinator in time, and he coordinates the subgroup meetings in his area.
University of Technology Aachen: Manfred Nagl (team leader), Andy Schürr, Andreas Winter, Bernhard Westfechtel, Carl-Arndt Krapp
University of Antwerp: Dirk Janssens, Jan Paredaens (team leaders), Jan Van den Bussche, Marc Gemis
Technical University of Berlin: Hartmut Ehrig, Herbert Weber (team leaders), Ingo Claßen, Michael Löwe, Julia Padberg, Gabi Taentzer, Reiko Heckel, Jürgen Müller, Annika Wagner
University of Bremen: Otthein Herzog (team leader), Hans-Jörg Kreowski (team leader and Working Group coordinator), Detlef Plump (Working Group manager), Frank Drewes, Berthold Hoffmann, Christoph Klauck, Renate Klempien-Hinrichs, Sabine Kuske
University of Leiden: Gregor Engels, Grzegorz Rozenberg (team leaders), Marc Andries, Egbert Boers, Joost Engelfriet, Jetty Kleijn, Pieter Koopman, Jan Rekers, Andreas Zamperoni, Vincent Zweije
University of Nijmegen: Rinus Plasmeijer (team leader), Marko van Eekelen, Sjaak Smetsers, Erik Barendsen, John van Groningen, Peter Achten, Marco Pil, Pascal Serrarens, Ronny Wichers Schreur
University of Pisa: Ugo Montanari (team leader), Roberto Bruni, Andrea Corradini, Andrea Maggiolo Schettini, Marco Pistore, Pantaleone Rosa, Francesca Rossi
University of Rome: Francesco Parisi-Presicce (team leader), Stefano Levialdi, Piero Mussio, Luigi Cinque, Paolo Bottoni
The table below indicates to which of the topics and subtopics the teams will contribute.
| Language issues | Tool issues | Application domains | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1.1 | 1.2 | 1.3 | 1.4 | 2.1 | 2.2 | 2.3 | 2.4 | 3.1 | 3.2 | 3.3 | 3.4 | 3.5 | 3.6 | |
| Aachen | * | * | * | * | * | * | * | * | * | * | * | * | ||
| Antwerp | * | * | * | * | ||||||||||
| Berlin | * | * | * | * | * | * | * | |||||||
| Bremen | * | * | * | * | * | * | * | * | ||||||
| Leiden | * | * | * | * | * | * | * | * | * | * | * | |||
| Nijmegen | * | * | * | * | * | * | * | |||||||
| Pisa | * | * | * | * | * | * | ||||||||
| Rome | * | * | * | * | * | * | * | * | * | |||||
APPLIGRAPH will correspond and cooperate with other experts in the field and related applied areas. The list of scientific correspondents includes: Virginio Cantoni (Pavia, Italy), Heiko Dörr (Daimler-Benz AG, Berlin, Germany), Maria Francesca Costabile (Bari, Italy), Jürgen Ebert (Koblenz, Germany), Herbert Göttler (Mainz, Germany), Marc Gyssens (Limburg, Belgium), Annegret Habel (Hildesheim, Germany), T. Harju (Turku, Finland), Neil Jones (DIKU, Denmark), Simon Peyton Jones (Glasgow, Great Britain), Alfonso Pierantonio (L'Aquila, Italy), Wilhelm Schäfer (Paderborn, Germany), Hans-Jürgen Schneider (Erlangen, Germany), Gabriel Valiente Feruglio (Barcelona, Spain)
[CM95] Andrea Corradini, Ugo Montanari, editors. Proc. Final Workshop of the ESPRIT BR Working Groups SEMAGRAPH II and COMPUGRAPH II (SEGRAGRA '95). Elsevier, 1995.
[EKR91] Hartmut Ehrig, Hans-Jörg Kreowski, Grzegorz Rozenberg, editors. Proc. Fourth Intl. Workshop on Graph Grammars and Their Application to Computer Science, volume 532 of Lecture Notes in Computer Science. Springer, 1991.
[ENR83] Hartmut Ehrig, Manfred Nagl, Grzegorz Rozenberg, editors. Proc. Second Intl. Workshop on Graph Grammars and Their Application to Computer Science, volume 153 of Lecture Notes in Computer Science. Springer, 1983.
[ENRR87] Hartmut Ehrig, Manfred Nagl, Grzegorz Rozenberg, Azriel Rosenfeld, editors. Proc. Third Intl. Workshop on Graph Grammars and Their Application to Computer Science, volume 291 of Lecture Notes in Computer Science. Springer, 1987.
[SE94] Hartmut Ehrig, Hans Jürgen Schneider, editors. Proc. Intl. Workshop on Graph Transformations in Computer Science, volume 776 of Lecture Notes in Computer Science. Springer, 1994.
[Ha92] Annegret Habel. Hyperedge Replacement: Grammars and Languages, volume 643 of Lecture Notes in Computer Science. Springer, Berlin, 1992.
[PvE93] Rinus Plasmeijer, Marko van Eekelen. Functional Programming and Parallel Graph Rewriting. International Computer Science Series. Addison-Wesley, Amsterdam, 1993.
[SPE93] Ronan Sleep, Rinus Plasmeijer, Marko van Eekelen, editors. Term Graph Rewriting, Theory and Practice. Wiley & Sons, Chichester, New York, Brisbane, Toronto, Singapore, 1993.