Categorical approach to horizontal structuring and refinement of high-level replacement systems.

*(English)*Zbl 0941.18001Summary: Based on the well-known theory of high-level replacement systems – a categorical formulation of graph grammars – we present new results concerning refinement of high-level replacement systems. Motivated by Petri nets, where refinement is often given by morphisms, we give a categorical notion of refinement. This concept is called \(Q\)-transformations and is established within the framework of high-level replacement systems. The main idea is to supply rules with an additional morphism, which belongs to a specific class \({\mathcal Q}\) of morphisms. This leads to the new notions of \({\mathcal Q}\)-rules and \({\mathcal Q}\)-transformations. Moreover, several concepts and results of high-level replacement systems are extended to \({\mathcal Q}\)-transformations. These are sequential and parallel transformations, union, and fusion, based on different colimit constructions. The main results concern the compatibility of these constructions with \({\mathcal Q}\)-transformations that is the corresponding theorems for usual transformations are extended to \({\mathcal Q}\)-transformations. Finally, we demonstrate the application of these techniques for the special case of Petri nets to a case study concerning the requirements engineering of a medical information system.

##### MSC:

18A10 | Graphs, diagram schemes, precategories |

68Q85 | Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) |

94C99 | Circuits, networks |

18A30 | Limits and colimits (products, sums, directed limits, pushouts, fiber products, equalizers, kernels, ends and coends, etc.) |

68Q42 | Grammars and rewriting systems |