Graph transformation systems are widely recognized as a powerful formalism for the specification of concurrent and distributed systems. Therefore, the need emerges naturally of developing formal concurrent semantics for graph transformation systems allowing for a suitable description and analysis of their computational properties. The aim of this chapter is to review and compare various concurrent semantics for the double pushout (DPO) algebraic approach to graph transformation, using different mathematical structures and describing computations at different levels of abstraction. We first present a trace semantics, based on the classical shift equivalence on graph derivations. Next we introduce graph processes, which lift to the graph transformation framework the notion of non-sequential process for Petri nets. Trace and process semantics are shown to be equivalent, in the sense that given a graph transformation system, the corresponding category of derivation traces and that of (concatenable) processes turns out to be isomorphic. Finally, a more abstract description of graph transformation systems computations is given by defining a semantics based on Winskel's event structures.

Concurrent semantics of algebraic graph transformations

BALDAN, PAOLO;ROSSI, FRANCESCA
1999

Abstract

Graph transformation systems are widely recognized as a powerful formalism for the specification of concurrent and distributed systems. Therefore, the need emerges naturally of developing formal concurrent semantics for graph transformation systems allowing for a suitable description and analysis of their computational properties. The aim of this chapter is to review and compare various concurrent semantics for the double pushout (DPO) algebraic approach to graph transformation, using different mathematical structures and describing computations at different levels of abstraction. We first present a trace semantics, based on the classical shift equivalence on graph derivations. Next we introduce graph processes, which lift to the graph transformation framework the notion of non-sequential process for Petri nets. Trace and process semantics are shown to be equivalent, in the sense that given a graph transformation system, the corresponding category of derivation traces and that of (concatenable) processes turns out to be isomorphic. Finally, a more abstract description of graph transformation systems computations is given by defining a semantics based on Winskel's event structures.
1999
Handbook of Graph Grammars and Computing by Graph Transformation, Vol. III: Concurrency, Parallellism, and Distribution.
9789810240219
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/162227
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact