Graph rewriting in some categories of partial morphisms. (English) Zbl 0765.68065
Graph grammars and their application to computer science, Proc. 4th Int. Workshop, Bremen/Ger. 1990, Lect. Notes Comput. Sci. 532, 490-504 (1991).
Summary: [For the entire collection see Zbl 0753.00023.]
We present a definition of term graph rewriting as the taking of a pushout in a category of partial morphisms, adapting the rather ad hoc definitions we gave in [Theor. Comput. Sci. 52, 37-58 (1987; Zbl 0636.68028)] so as to use a standard category-theoretic concept of partial morphism. This single-pushout construction is shown to coincide with the well-known double-pushout description of graph rewriting whenever the latter is defined. In general, the conditions for the single pushout to exist are weaker than those required for the double pushout. In some categories of graphs, no conditions at all are necessary.
We present a definition of term graph rewriting as the taking of a pushout in a category of partial morphisms, adapting the rather ad hoc definitions we gave in [Theor. Comput. Sci. 52, 37-58 (1987; Zbl 0636.68028)] so as to use a standard category-theoretic concept of partial morphism. This single-pushout construction is shown to coincide with the well-known double-pushout description of graph rewriting whenever the latter is defined. In general, the conditions for the single pushout to exist are weaker than those required for the double pushout. In some categories of graphs, no conditions at all are necessary.
MSC:
| 68Q42 | Grammars and rewriting systems |
| 18A20 | Epimorphisms, monomorphisms, special classes of morphisms, null morphisms |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C65 | Hypergraphs |
