Pullback as a Generic Graph Rewriting Mechanism

摘要

Rewriting usually relies on a notion of substitution which can be understood as the succession of three basic operations: deletion of the part to be rewritten to provide a context, union of this context with the right-hand side of a rule, liaison of those two parts, most often by identification of some corresponding items. In the field of graph rewriting, this has led to the elegant, productive and therefore popular method known as the double push-out approach to graph rewriting. Yet this method has met its descriptive limits when trying to deal with the various notions of node replacement. In this paper we show how - when set in a proper framework - products (or pullbacks) can provide a very generic and uniform rewriting mechanism which extends uniformly to arbitrary complicated graph-like structures.