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.
Equivalence and independence in controlled graph-rewriting processes
Corradini, Andrea;
2018-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
2018-LNCS-ICGT-POST-Kulcsár2018_Chapter_EquivalenceAndIndependenceInCo.pdf
Open Access dal 30/05/2019
Tipologia:
Documento in Post-print
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
681.13 kB
Formato
Adobe PDF
|
681.13 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.