Algebraic approach to single-pushout graph transformation (Q685460): Difference between revisions

The paper, which is a summary of the PhD thesis of the author, gives an important contribution to the field of graph grammars in general, and to the algebraic (categorical) approach in particular. A graph rewrite rule is defined as a partial graph morphism, and, given an occurrence of the lhs of the rule in a graph (i.e., a total morphism from the lhs to that graph), a graph rewriting step is modeled by the pushout of the rule and the occurrence morphisms in the category of graphs and partial morphisms. This generalizes the classical ``double-pushout approach'' (shortly DPO), where a rule is a pair of coinitial total graph morphisms, and a graph rewriting step is modeled by a diagram consisting of two pushouts. Although one has to work with partial instead of total morphisms, the proposed approach turns out to be technically simpler. Indeed, many classical results to the DPO approach can be restated, and are easier to prove due to the simpler definition of rewriting (these include parallel derivations and amalgamation of productions). As for the expressive power, the proposed approach allows to model the deletion of a subgraph in an unknown context, which is not possible in the other approach. In order to generalize the single-pushout approach to other kinds of structures, categories of algebras and partial homomorphisms with respect to a given signature SIG are considered. An interesting result shows that if (and only if) all the operators in SIG are unary then the category of SIG-algebras and partial SIG-homomorphisms has all pushouts, and therefore the single-pushout approach can be extended to it. Signatures satisfying this requirement can specify graphs of various kinds, hypergraphs, and functional expressions.