Fundamentals of Algebraic Graph Transformation

Front Cover
Springer Science & Business Media, May 1, 2006 - Computers - 390 pages
0 Reviews

Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory.

Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool environment. Finally the appendix covers the basics of category theory, signatures and algebras.

The book addresses both research scientists and graduate students in computer science, mathematics and engineering.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

General Introduction
5
Graph Transformation Systems 37
36
5
77
Constraints and Application Conditions 151
150
Typed Attributed Graph Transformation Systems
168
Typed Attributed Graph Transformation Systems
181
Embedding and Local Confluence for Typed AGT Systems
207
Adhesive HLR Categories for Typed Attributed Graphs
221
14
287
Implementation of Typed Attributed Graph
305
A A Short Introduction to Category Theory 329
326
B A Short Introduction to Signatures and Algebras
353
Detailed Proofs
359
References
377
Index 385
384
Copyright

Constraints Application Conditions and Termination
237

Other editions - View all

Common terms and phrases

About the author (2006)

The first author, Prof. Hartmut Ehrig, has been one of the key figures in this specific field over the last few decades.

He has written over 200 articles for refereed publications in the last 30 years (http: //www.informatik.uni-trier.de/~ley/db/indices/a-tree/e/Ehrig: Hartmut.html).

He has edited many LNCS proceedings volumes over the last 20 years, including: LNCS 3393 (http: //www.springer.com/3-540-24936-2), LNCS 3256 (http: //www.springer.com/3-540-23207-9), LNCS 3147 (http: //www.springer.com/3-540-23135-8), LNCS 2505 (http: //www.springer.com/3-540-44310-X), LNCS 2472 (http: //www.springer.com/3-540-20538-1), LNCS 2128 (http: //www.springer.com/3-540-43067-9), LNCS 1764 (http: //www.springer.com/3-540-67203-6), LNCS 1073 (http: //www.springer.com/3-540-61228-9), LNCS 776 (http: //www.springer.com/3-540-57787-4), LNCS 534 (http: //www.springer.com/3-540-54496-8), LNCS 532 (http: //www.springer.com/3-540-54478-X), LNCS 393 (http: //www.springer.com/3-540-51722-7), LNCS 291 (http: //www.springer.com/3-540-18771-5). These LNCS volumes deal with his particular areas of expertise: Petri nets, graph transformations, category theory, graph grammars, type specification, and software modelling and specification techniques.

He was the subject of the recent LNCS Festschrift: Formal Methods in Software and Systems Modeling, Essays Dedicated to Hartmut Ehrig on the Occasion of His 60th Birthday, LNCS 3393, Kreowski et al., 2005 (http: //www.springer.com/3-540-24936-2).

Prof. Ehrig wrote two previous books for Springer's EATCS series: (i) "Fundamentals of Algebraic Specification 2 -- Module Specifications and Constraints," EATCS Monographs Series, Hartmut Ehrig, Bernd Mahr, 1990, http: //www.springer.com/3-540-51799-5; this sold 1151 copies. (ii) "Fundamentals of Algebraic Specification 1 -- Equations and Initial Semantics," EATCS Monographs Series, Hartmut Ehrig, Bernd Mahr, http: //www.springer.com/3-540-13718-1.

He has been a key promoter of the relevant research area of the book in various EU-funded projects, including COMPUGRAPH (http: //www.sts.tu-harburg.de/projects/Esprit-BR/Synopses/Projects/7183.html).

Finally, Prof. Ehrig was among the coeditors of the World Scientific "Handbook of Graph Grammars and Computing by Graph Transformation."

The fourth author, Dr. Gabriele Taentzer, has written over 50 articles for refereed publications in the last 15 years (http: //www.informatik.uni-trier.de/~ley/db/indices/a-tree/t/Taentzer: Gabriele.html), including the ACM Computing Surveys paper "Graphical Representation and Graph Transformation." Dr. Taentzer is on the Program and Steering Committees of a number of key, relevant conferences (FASE 2006, ICGT 2006), etc.

Further Notes: Prof. Dr. Hartmut Ehrig, TU Berlin, http: //tfs.cs.tu-berlin.de/; Karsten Ehrig, TU Berlin, http: //tfs.cs.tu-berlin.de/~karstene; Ulrike Prange, TU Berlin, http: //tfs.cs.tu-berlin.de/~uprange; Dr. Gabriele Taentzer, TU Berlin, http: //tfs.cs.tu-berlin.de/~gabi.