The dynamic behavior of rule-based systems (like term rewriting systems, process algebras, and so on) can be traditionally determined in two orthogonal ways. Either operationally, in the sense that a way of embedding a rule into a state is devised, stating explicitly how the result is built: This is the role played by (the application of) a substitution in term rewriting. Or inductively, showing how to build the class of all possible reductions from a set of basic ones: For term rewriting, this is the usual definition of the rewrite relation as the minimal closure of the rewrite rules. As far as graph transformation is concerned, the operational view is by far more popular: In this paper we lay the basis for the orthogonal view. We first provide an inductive description for graphs as arrows of a freely generated dgs-monoidal category. We then apply 2-categorical techniques, already known for term and term graph rewriting, recasting in this framework the usual description of graph transformation via double-pushout.
An inductive view of graph transformation
GADDUCCI, FABIO;
1997-01-01
Abstract
The dynamic behavior of rule-based systems (like term rewriting systems, process algebras, and so on) can be traditionally determined in two orthogonal ways. Either operationally, in the sense that a way of embedding a rule into a state is devised, stating explicitly how the result is built: This is the role played by (the application of) a substitution in term rewriting. Or inductively, showing how to build the class of all possible reductions from a set of basic ones: For term rewriting, this is the usual definition of the rewrite relation as the minimal closure of the rewrite rules. As far as graph transformation is concerned, the operational view is by far more popular: In this paper we lay the basis for the orthogonal view. We first provide an inductive description for graphs as arrows of a freely generated dgs-monoidal category. We then apply 2-categorical techniques, already known for term and term graph rewriting, recasting in this framework the usual description of graph transformation via double-pushout.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
