Fundamentals of algebraic graph transformation (Q2491953)

Graph grammars have been extensively studied in the last forty years for a number of reasons. In analogy with string rewriting rules for strings over a finite alphabet, graph transformations extend to treat structures that are more complex than the linear string structure. Consequently graph grammars have evolved in a number of specific settings, such as representations of pictorial data, of process structure, and of relational structure. Concurrently a general theory of graph transformations that transcends the specifics of each application has been developed. This book treats that general theory. As the title suggests, its focus is on the fundamentals and on their theoretical underpinnings in category theory. It is a very clear exposition of this material, spanning the breadth from underlying mathematics to an applications case study. The book is divided into four parts. The first one, Introduction to graph transformation systems, begins in Chapter 1 with an accessible introduction for the reader being new to the area. The treatment of the many different means by which graph transformations can be specified is lucid. A first view of the generalization from graphs to categories is provided. Then Chapter 2 develops the basic structures to be examined: graphs, morphisms, and typed graphs. A basic ``gluing'' construction is introduced to set the stage for the introduction of category theory. Chapter 3 then describes the classical view of graph transformations, including the main theorems. This material is presented in a manner that minimizes (for the moment) the category-theoretic requirements. Part II, Adhesive HLR categories and systems, develops the fundamental general notions in the setting of category theory. Chapter 4 gives the axiomatic definitions, and establishes their generality through a number of different instantiations (graphs, typed graphs, Petri nets, hypergraphs, and the like). Chapter 5 treats independence and parallelism in this general setting (thereby extending the results of Chapter 3). Chapter 6 further treats embedding and extension theorems for the same general setting. Chapter 7 then introduces and explores constraints. While Part II provides the underlying theoretical basis, the material in Parts I and II has been organized so that a reader can skip Part II and proceed to the remaining parts, although the formal justifications needed may be omitted if that is done. Part III, Typed attributed graph transformation systems, specializes the theory of Part II to an important case, typed attributed graphs. Nodes and edges have both types and attributes in this model, and the application of transformations depends on both the typing and the attribution. Chapter 8 develops the formal definition as a category, and Chapters 9 and 10 then extend all the results from the classical theory in Chapter 3 to this setting. The proofs of these statements follow in Chapter 11 by demonstrating that the category is one of the adhesive HLR categories examined in Part II. Chapter 12 extends the model to handle constraints, and Chapter 13 introduces inheritance and the resulting computational efficiencies obtained. Part IV, Case study and tool support, pursues the specific systems from Part III in two directions. Chapter 14 provides a case study of the transformation of statecharts to Petri nets; the explanations here are of great value in providing examples for the material in Part III, and provide evidence for the merit of the approaches taken. Chapter 15 then describes a software tool, AGG, for the automation of such transformation systems. Extensive appendices then provide a quick tour of category theory and detailed proofs for some of the statements in the main text. A good bibliography is provided. Unfortunately there is no glossary of frequently used terms, and the index is quite short (3.5 pages), so the novice reader will frequently need to undertake a linear search for an unknown term. This makes it difficult to open the book at a random page and start reading; as the authors note, many of the basic ideas (graphs, types, attributes, and so on) have different interpretations in the literature, but often a specific meaning in the context in which they are used in the book. Despite this concern, the overall structure of the book provides a logical development that can be followed with reasonable effort. The authors have done a very good job of presenting an area in which many different threads of research have developed into a general theory, one that has numerous applications and a solid theoretical foundation. The book provides a helpful roadmap to the published research in the area, and a systematic treatment that emphasizes the fundamentals as the authors promised.