Composition and Decomposition of DPO Transformations with Borrowed Context

Paolo Baldan⁽¹⁾ - Hartmut Ehrig⁽²⁾ - Barbara König⁽³⁾

⁽¹⁾Dipartimento di Informatica, Università Ca' Foscari di Venezia, Italia.
⁽²⁾Institut für Softwaretechnik und Theoretische Informatik, Technische~Universität Berlin, Germany.
⁽³⁾Institut für Informatik und interaktive Systeme, Universität Duisburg-Essen, Germany.

Abstract:

Double-pushout (DPO) transformations with borrowed context extend the standard DPO approach by allowing part of the graph needed in a transformation to be borrowed from the environment. The bisimilarity based on the observation of borrowed contexts is a congruence, thus facilitating system analysis. In this paper, focusing on the situation in which the states of a global system are built out of local components, we show that DPO transformations with borrowed context defined on a global system state can be decomposed into corresponding transformations on the local states and vice versa. Such composition and decomposition theorems, developed in the framework of adhesive categories, can be seen as a first step towards an inductive definition, in SOS style, of the labelled transition system associated to a graph transformation system. As a special case we show how an ordinary DPO transformation on a global system state can be decomposed into local DPO transformations with borrowed context using the same production.