Categorical approach to horizontal structuring and refinement of high-level replacement systems. (English) Zbl 0941.18001

Summary: 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.


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
Full Text: DOI