On categorical graph grammars integrating structural transformations and operations on labels (Q685458)

Transformations of graphs can be done by applying productions of a graph grammar. The application of a production replaces an occurrence of its left-hand side by its right-hand side. Now, graphs are a means to represent systems of asynchronous processes, and graph transformations can describe system behaviours. In order to describe systems that share data structures one must overcome the limitations of working with label-preserving graph morphisms. The present paper extends previous work in which, in order to allow variables in productions, a simple structure is imposed on the set of labels and graph morphisms are required to be compatible with this structure. In the present paper labelling is done in categories rather than in an alphabet and, in this way, operations can be performed on the labels while the graphs are rewritten. A pair of categories \({\mathbf L}=({\mathbf L}_ E\), \({\mathbf L}_ V)\) is assumed with object sets the set of edge labels and node labels, respectively. A category of \({\mathbf L}\)-labelled graphs and \({\mathbf L}\)-morphisms is considered and some fundamental properties are proved. Also the more general case in which labels are graphs is considered and the category \({\mathbf G}\)-Graph is defined. Of special interest are the categories which satisfy the parallel independence theorem (PIT) with respect to a class of distinguished morphisms. The category \({\mathbf G}\)-Graph is shown to be a PIT category with respect to a suitable class of morphisms. The usefulness of the approach is demonstrated by modelling condition/event nets and plasce/transition nets in the above described framework.