Several applications of graph rewriting systems (notably, some encodings of calculi with name passing) require rules which, besides deleting and generating graph items, are able to coalesce some parts of the graph. This latter feature forbids the development of a satisfactory concurrent semantics for rewrites (intended as a partial order description of the steps in a computation). This paper proposes the use of graphs with equivalences, i.e., (typed hyper-) graphs equipped with an equivalence over nodes, for the analysis of distributed systems. The formalism is amenable to the tools of the double-pushout approach to rewriting, including the theoretical results associated to its concurrent features. The formalism is tested against the encoding of a simple calculus with name mobility, namely the solo calculus.

Concurrent Rewriting for Graphs with Equivalences

BALDAN, PAOLO;
2006

Abstract

Several applications of graph rewriting systems (notably, some encodings of calculi with name passing) require rules which, besides deleting and generating graph items, are able to coalesce some parts of the graph. This latter feature forbids the development of a satisfactory concurrent semantics for rewrites (intended as a partial order description of the steps in a computation). This paper proposes the use of graphs with equivalences, i.e., (typed hyper-) graphs equipped with an equivalence over nodes, for the analysis of distributed systems. The formalism is amenable to the tools of the double-pushout approach to rewriting, including the theoretical results associated to its concurrent features. The formalism is tested against the encoding of a simple calculus with name mobility, namely the solo calculus.
2006
CONCUR 2006
3540373764
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11577/145059
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact