Subobject transformation systems (Q934672)

Subobject Transformation Systems (STS) are presented as a new formal framework for the analysis of derivations of transformation systems based on the algebraic double-pushout (DPO). In the third section of their paper, the authors use them in order to identify some possible relations among rules. These are used to define other derived relations which are shown to coincide with those introduced in the literature for STS arising as processes of DPO rewriting systems. An interesting and useful auxiliary graphical ``Venn-diagram'' like notation for reasoning about dependency relations is presented, as well as the notion of region which is, roughly, a complement of a subobject. The basic theory of regions allows the authors to prove that reasoning with the aid of the Venn-diagrams is sound. Conditions are discussed under which two productions of an STS have to be considered as independent; several equivalent ways to characterize this relation are given. A colimit construction is also presented that builds an STS from a given derivation tree of a DPO system, generalizing the construction of the process of a linear derivation proposed in the literature. Finally, the authors prove that the analysis of the relationships among rule occurrences in the derivation tree can be reduced faithfully to the analysis of such relationships in the generated STS.