We compare the expressive power of Hoare (i.e., CSP style) and Milner (i.e., CCS style) synchronizations for defining graph transformations in a framework where edges can perform actions on adjacent nodes to synchronize their evolutions. Furthermore, nodes can be communicated and merged. We show that the expressive powers of the two synchronization models are different, but no one is greater than the other. Finally, we show that in many interesting cases the behaviour of a synchronization model can be mimicked by the other one using suitable translations for the rewritten graphs.
Hoare vs Milner: Comparing Synchronizations in a Graphical Framework with Mobility / LANESE I.; MONTANARI U.. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - ELETTRONICO. - 154:2(2006), pp. 55-72. (Intervento presentato al convegno GT-VC'05, Graph Transformation for Verification and Concurrency tenutosi a San Francisco, California, USA nel 23-26/8/2005) [10.1016/j.entcs.2005.03.032].
Hoare vs Milner: Comparing Synchronizations in a Graphical Framework with Mobility
LANESE, IVAN;
2006
Abstract
We compare the expressive power of Hoare (i.e., CSP style) and Milner (i.e., CCS style) synchronizations for defining graph transformations in a framework where edges can perform actions on adjacent nodes to synchronize their evolutions. Furthermore, nodes can be communicated and merged. We show that the expressive powers of the two synchronization models are different, but no one is greater than the other. Finally, we show that in many interesting cases the behaviour of a synchronization model can be mimicked by the other one using suitable translations for the rewritten graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
