Modelling Calculi with Name Mobility using Graphs with Equivalences
P. Baldan (1) -
F. Gadducci(2) -
U. Montanari(2)
(1) Dipartimento di Informatica, Università Ca' Foscari di Venezia, Italia. (2) Dipartimento di Informatica, Università di Pisa, Italia.
Abstract:
In the theory of graph rewriting, the use of coalescing rules, i.e.,
of rules which besides deleting and generating graph items, can
coalesce some parts of the graph, turns out to be quite useful for
modelling purposes, but, at the same time, problematic for the
development of a satisfactory partial order concurrent semantics for
rewrites. Rewriting over graphs with equivalences, i.e., (typed
hyper)-graphs equipped with an equivalence over nodes provides a
technically convenient replacement of graph rewriting with coalescing
rules, for which a truly concurrent semantics can be easily
defined. The expressivity of such a formalism is tested in a setting
where coalescing rules typically play a basic role: the encoding of
calculi with name passing as graph rewriting systems. Specifically, we
show how the (monadic fragment) of the solo calculus, one of the
dialect of those calculi whose distinctive feature is name fusion, can
be encoded as a rewriting system over graph with equivalences.