Categorical Abstract Rewriting Systems and Functoriality of Graph Transformation

Abstract

Abstract rewriting systems are often defined as binary relations over a given set of objects. In this paper, we introduce a new notion of abstract rewriting system in the framework of categories. Then, we define the functoriality property of rewriting systems. This property is sometimes called vertical composition. We show that most graph transformation systems are functorial and provide a counter-example of graph transformation system which is not functorial.