Date of publication: 1996-10-01

Date: 1996-10

Abstract:

A relationship between double-pushout rewriting of total and partial hypergraphs is established by means of free completions. Given a double-pushout transformation rule P of total hypergraphs, a corresponding double-pushout transformation rule P' of partial subhypergraphs can be found a priori such that double-pushout derivations by the application of P are free completions of double-pushout derivations by the application of P'. It allows a more efficient double-pushout rewriting of total hypergraphs by rewriting suitable partial hypergraphs and freely completing the resulting partial hypergraphs. The main results in this paper are actually established in the more general setting of hierarchical unary algebras.]]>

Date: 1996-10

Date: 1996-10

Abstract:

The transformation of total graph structures has been studied from the algebraic point of view over more than two decades now, and it has motivated the development of the so-called double-pushout and single-pushout approaches to graph transformation.

The transformation of total graph structures has been studied from the algebraic point of view over more than two decades now, and it has motivated the development of the so-called double-pushout and single-pushout approaches to graph transformation. In this article we extend the double-pushout approach to the algebraic transformation of partial many-sorted unary algebras. Such a generalization has been motivated by the need to model the transformation of structures which are richer and more complex than acyclic graphs and hypergraphs. The main result presented in this article is an algebraic characterization of the double-pushout transformation in the categories of all homomorphisms and all closed homomorphisms of unary partial algebras over a given signature, together with a corresponding operational characterization which may serve as a basis for implementation. Moreover, both categories are shown to satisfy the strongest of the HLR (High Level Replacement) conditions with respect to closed monomorphisms. HLR conditions are fundamental to rewriting because they guarantee the satisfaction of many rewriting theorems concerning confluence, parallelism and concurrency.]]>

Dagstuhl Seminar 9637 on Graph Transformations in Computer Science

Presentation's date: 1996-09-09

Lecture notes in computer science

Vol. 1073, num. 1, p. 1-15

Date of publication: 1996-07

Tugboat

Vol. 17, num. 2, p. 191-199

Date of publication: 1996-06

Date: 1996-06

Abstract:

The single-pushout approach to graph transformation is extended to the algebraic transformation of partial many-sorted unary algebras. The main result presented in this article is an algebraic characterization of the single-pushout transformation in the categories of all conformisms, all closed quomorphisms, and all closed-domain closed quomorphisms of unary partial algebras over a given signature, together with a corresponding operational characterization that may serve as a basis for implementation. Moreover, all three categories are shown to satisfy all of the HLR (High Level Replacement) conditions for parallelism, taking as occurrences the total morphisms in each category. Another important result presented in this article is the definition of HLR conditions for amalgamation, which are also satisfied by the categories of partial homomorphisms considered here, taking again the corresponding total morphisms as occurrences.]]>

Date: 1996-03

Abstract:

Single-pushout transformation in a category of spans, in some sense a generalization of the usual notion of partial morphism, is studied in this paper. Contrary to the usual notion of partial morphism, spans are single objects instead of equivalence classes. A necessary condition for the existence of the pushout of two spans is established which involves properties of the base category, from which the category of spans is derived, as well as properties of the spans themselves. Several interesting categories of partial morphisms of hypergraphs are proved to satisfy the necessary condition.]]>

Dagstuhl Seminar 9637 on Graph Transformations in Computer Science

p. 8