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
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
0.9816506
0 references
0.94738907
0 references
0.9237398
0 references
0.8995855
0 references
0.89821416
0 references
0.8791233
0 references
0 references
0.86946666
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