Handbook of graph grammars and computing by graph transformations. Vol. 1: Foundations.

*(English)*Zbl 0908.68095
Singapore: World Scientific (ISBN 981-02-2884-8/hbk; 978-981-238-472-0/ebook). xv, 553 p. (1997).

Graphs are well known as a flexible and intuitive means to represent structured data. However, in practice static situations occur rather seldomly. In most cases data and, even more important, their relations are subject to changes reflecting the behaviour of the modelled system. While the use of graphs has become very common in modern software design these dynamical aspects are usually handled in an ad-hoc way.

The theory of graph grammars and graph transformations arose from the wish to overcome this unsatisfactory situation by providing a sound theoretical basis for the specification of systems which generate and transform graphs. During the last three decades this research has led to a rich and interesting theory with numerous potential applications. Unfortunately, despite the simplicity of the basic ideas, the theory was rather inaccessible for the non-specialist for a long time because no comprehensive presentation of the field was available.

The book under review closes this gap by presenting the main parts of the theoretical foundations of graph grammars and graph transformations in a comprehensible way. The book is therefore recommended to everyone who wants to apply graph transformations in practice, but also, as a valuable collection of up-to-date surveys, to researchers who want to work in the field.

The seven chapters of the book cover context-free graph generation (chapters 1 and 2), the so-called algebraic approach to graph transformation (chapters 3 and 4), the use of monadic second-order logic to express graph properties and transformations (chapter 5), 2-structures as a generalisation of graphs (chapter 6), and programmed graph replacement systems (chapter 7).

The theory of graph grammars and graph transformations arose from the wish to overcome this unsatisfactory situation by providing a sound theoretical basis for the specification of systems which generate and transform graphs. During the last three decades this research has led to a rich and interesting theory with numerous potential applications. Unfortunately, despite the simplicity of the basic ideas, the theory was rather inaccessible for the non-specialist for a long time because no comprehensive presentation of the field was available.

The book under review closes this gap by presenting the main parts of the theoretical foundations of graph grammars and graph transformations in a comprehensible way. The book is therefore recommended to everyone who wants to apply graph transformations in practice, but also, as a valuable collection of up-to-date surveys, to researchers who want to work in the field.

The seven chapters of the book cover context-free graph generation (chapters 1 and 2), the so-called algebraic approach to graph transformation (chapters 3 and 4), the use of monadic second-order logic to express graph properties and transformations (chapter 5), 2-structures as a generalisation of graphs (chapter 6), and programmed graph replacement systems (chapter 7).

Reviewer: F.Drewes (Bremen)

##### MSC:

68Q42 | Grammars and rewriting systems |

68-06 | Proceedings, conferences, collections, etc. pertaining to computer science |

00B15 | Collections of articles of miscellaneous specific interest |