Some Essentials of Graph Transformation

Summary. This chapter introduces rule-based graph transformation, which constitutes a well-studied research area in computer science. The chapter presents the most fundamental denitions and illustrates them with some selected examples. It presents also the concept of transformation units, which makes pure graph transformation more feasible for specication and modeling aspects. Moreover, a translation of Chomsky grammars into graph grammars is given and the main theorems concerning parallelism and concurrency are presented. Finally, an introduction to hyperedge replacement is given, a concept which has nice properties because it transforms hypergraphs in a context-free way.