Algebraic approach to graph transformation based on single pushout derivations (Q4028126)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 139800
Language Label Description Also known as
default for all languages
No label defined
    English
    Algebraic approach to graph transformation based on single pushout derivations
    scientific article; zbMATH DE number 139800

      Statements

      0 references
      0 references
      28 March 1993
      0 references
      graph grammars
      0 references
      graph rewriting
      0 references
      category of graphs and partial morphisms
      0 references
      partial graph morphism
      0 references
      asynchronous parallel derivations
      0 references
      single-pushout approach
      0 references
      categories of algebras and partial homomorphisms
      0 references
      hypergraphs
      0 references
      functional expressions
      0 references
      Algebraic approach to graph transformation based on single pushout derivations (English)
      0 references
      [For the entire collection see Zbl 0747.00042.] Various approaches have been proposed in the last two decades to formalize the notion of graph rewriting, which extends the theory of formal languages in order to deal with structures more general than strings, like graphs and maps. Among them, one of the most successful is the so-called ``double-pushout approach'' (shortly DPO), where a graph rewrite rule is represented by a pair of total graph morphism having the same source, and a graph rewriting step is modeled by a diagram consisting of two pushouts in the category of graphs and total graph morphisms. The paper introduces a new approach to graph rewriting (developed by the first author in his PhD thesis), based on categorical constructions in the category of graphs and partial morphisms. A graph rewrite rule is defined simply as a partial graph morphism, and, given an occurrence of the lhs of the rule in the 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. It is shown that this definition of rewriting is strictly more powerful than the one of the DPO approach: as for the expressive power, it allows to model the deletion of a subgraph in an unknown context, which is not possible in the other approach. The paper shows moreover that, unlike in the DPO approach, synchronous parallel derivations increase the generative power of a graph rewriting system; that some proofs of classical results are easier due to the simpler definition of rewriting; and that asynchronous parallel derivations can be defined as well, in a natural way. In order to generalize the single-pushout approach to other kind of structures, categories of algebras and partial homomorphisms w.r.t. a given signature SIG are considered. An interesting result shows that if (and only if) all the operators of 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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references