Double-pushout hypergraph rewriting using total conformisms

Abstract

The algebraic transformation of hypergraphs, under the so-called double-pushout (DPO) approach, was invented more than two decades ago, and thoroughly developed since then. We introduce in this paper a new approach to DPO algebraic transformation of hypergraphs and, more in general, of unary partial algebras, which generalizes the aforementioned “classical” DPO approach to hypergraph transformation. While the classical approach was based on the (usual) homomorphisms of hypergraphs, our new approach is based on the total conformisms, a type of morphisms of hypergraphs imported from the theory of partial algebras, which can be described, roughly speaking, as those mappings between hypergraphs that “reflect” the structure of the target object. In this paper we give both an algebraic and an operational characterization of this new DPO transformation, first for unary partial algebras and then, as a particular case, for hypergraphs. We also study its abstract properties related to parallelism and concurrency through the determination of the HLR conditions it satisfies with respect to several natural classes of morphisms.