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

GADDUCCI, FABIO;MONTANARI, UGO GIOVANNI ERASMO
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.
File in questo prodotto:
File Dimensione Formato  
concur2006.pdf

solo utenti autorizzati

Tipologia: Versione finale editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 706.93 kB
Formato Adobe PDF
706.93 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

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: http://hdl.handle.net/11568/106094
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 4
social impact