Theory and Application of Graph Transformations

1. Front Matter

   PDF

2. Graph Languages

   1. Some Remarks on the Generative Power of Collage Grammars and Chain-Code Grammars

      • Frank Drewes

      Pages 1-14

   2. Tree Languages Generated by Context-Free Graph Grammars

      • Joost Engelfriet, Sebastian Maneth

      Pages 15-29

   3. Neighborhood Expansion Grammars

      • John L. Pfaltz

      Pages 30-44

   4. Neighborhood-Preserving Node Replacements

      • Konstantin Skodinis, Egon Wanke

      Pages 45-58

3. Graph Theory

   1. Complexity Issues in Switching of Graphs

      • Andrzej Ehrenfeucht, Jurriaan Hage, Tero Harju, Grzegorz Rozenberg

      Pages 59-70

   2. The Power of Local Computations in Graphs with Initial Knowledge

      • Emmanuel Godard, Yves Métivier, Anca Muscholl

      Pages 71-84

4. Categorical Approaches

   1. Double-Pullback Graph Transitions: A Rule-Based Framework with Incomplete Information

      • Hartmut Ehrig, Reiko Heckel, Mercè Llabrés, Fernando Orejas, Julia Padberg, Grzegorz Rozenberg

      Pages 85-102

   2. Double-Pushout Approach with Injective Matching

      • Annegret Habel, Jürgen Müller, Detlef Plump

      Pages 103-116

   3. Node Replacement in Hypergraphs: Translating NCE Rewriting into the Pullback Approacht

      • Hélène Jacquet, Renate Klempien-Hinrichs

      Pages 117-130

   4. Pushout Complements for Arbitrary Partial Algebras

      • Mercè Llabrés, Francesc Rosselló

      Pages 131-144

5. Concurrency and Distribution

   1. Unfolding of Double-Pushout Graph Grammars is a Coreflection

      • Paolo Baldan, Andrea Corradini, Ugo Montanari

      Pages 145-163

   2. Local Views on Distributed Systems and Their Communication

      • Ingrid Fischer, Manuel Koch, Gabriele Taentzer

      Pages 164-178

   3. Dynamic Change Management by Distributed Graph Transformation: Towards Configurable Distributed Systems

      • Gabriele Taentzer, Michael Goedicke, Torsten Meyer

      Pages 179-193

   4. A Framework for NLC and ESM: Local Action Systems

      • Nico Verlinden, Dirk Janssens

      Pages 194-214

6. Artificial Intelligence

   1. Redundancy and Subsumption in High-Level Replacement Systems

      • Hans-Jörg Kreowski, Gabriel Valiente

      Pages 215-227

   2. Knowledge Representation and Graph Transformation

      • Stefan Schuster

      Pages 228-237

   3. Utilizing Constraint Satisfaction Techniques for Efficient Graph Pattern Matching

      • Michael Rudolf

      Pages 238-251

7. Visual Languages

   1. Conceptual Model of the Graphical Editor GenGEd for the Visual Definition of Visual Languages

      • Roswitha Bardohl, Hartmut Ehrig

      Pages 252-266

   2. From Formulae to Rewriting Systems

      • Paolo Bottoni, Francesco Parisi-Presicce, Marta Simeoni

      Pages 267-280

Theareaofgraphtransformationoriginatedinthelate1960sunderthename “graph grammars” – the main motivation came from practical considerations concerning pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph transformation has grown impressively. The areas include: software speci?cation and development, VLSI layout schemes, database design, modeling of concurrent systems, m- sively parallel computer architectures, logic programming, computer animation, developmentalbiology,musiccomposition,distributedsystems,speci?cationl- guages, software and web engineering, and visual languages. As a matter of fact, graph transformation is now accepted as a fundamental computation paradigm where computation includes speci?cation, programming, and implementation. Over the last three decades the area of graph transfor- tion has developed at a steady pace into a theoretically attractive research ?eld, important for applications. Thisvolume consistsofpapersselectedfromcontributionsto the Sixth Int- national Workshop on Theory and Applications of Graph Transformation that took place in Paderborn, Germany, November 16-20, 1998. The papers und- went an additional refereeing process which yielded 33 papers presented here (out of 55 papers presented at the workshop). This collection of papers provides a very broad snapshot of the state of the art of the whole ?eld today. They are grouped into nine sections representing most active research areas. Theworkshopwasthe sixth in a seriesof internationalworkshopswhich take place every four years. Previous workshops were called “Graph Grammars and Their Application to Computer Science”. The new name of the Sixth Workshopre?ectsmoreaccuratelythecurrentsituation,whereboththeoryandapplication play an equally central role.

• Graph
• Graph grammar
• Graph theory
• artificial intelligence
• concurrent systems
• distributed computing
• formal methods
• grammar systems
• graph languages
• graph transformations
• intelligence
• system specifications
• visual languages

• Technische Universität Berlin, Germany

  Hartmut Ehrig

• University of Paderborn, Paderborn, Germany

  Gregor Engels

• Department of Computer Science, University of Bremen, Bremen, Germany

  Hans-Jörg Kreowski

• Leiden Center of Advanced Computer Science (LIACS), Leiden University, Leiden, The Netherlands

  Grzegorz Rozenberg

Policies and ethics