Graphs, Patterns and Rewriting
Guillaume Bonfante, Bruno Guillaume, Guy Perrier · 2018
This chapter provides the conceptual framework for a formal definition of graph rewriting. It demonstrates certain consequences associated with the characteristics of rewriting as presented in the GREW system, including termination and confluence. Unlike other forms of rewriting (terms, words, etc.), there is no common agreement on the definition of graph rewriting. The notion of graph morphism is used to describe pattern matching. Injective morphisms are the key to pattern matching. The image of the morphism is the part of the graph which corresponds precisely to the pattern. Injectivity indicates that all of the nodes in a pattern are distinct in the target graph. An imperative-type elementary command language is used to describe local transformations of the image graph. The chapter shows how the nodes of graph may be decomposed into distinct subsets. It focuses on the notion of strategies as used in GREW.