Equivalence and independence in controlled graph-rewriting processes

Graph transformation systems (GTS) are often defined as sets of rules that can be applied repeatedly and non-deterministically to model the evolution of a system. Several semantics proposed for GTSs are relevant in this case, providing means for analysing the system’s behaviour in terms of dependencies, conflicts and potential parallelism among the relevant events. Several other approaches equip GTSs with an additional control layer useful for specifying rule application strategies, for example to describe graph manipulation algorithms. Almost invariably, the latter approaches consider only an input-output semantics, for which the above mentioned semantics are irrelevant. We propose an original approach to controlled graph transformation, where we aim at bridging the gap between these two complementary classes of approaches. The control is represented by terms of a simple process calculus. Expressiveness is addressed by encoding in the calculus the Graph Processes defined by Habel and Plump, and some initial results are presented relating parallel independence with process algebraic notions like bisimilarity.