Graph grammars are the generalization of string grammars to graphs. Besides of generating graph languages, they can be used for the specification of concurrent and distributed systems. In this respect, they are far more expressive than, for example, Petri nets. In fact, they allow for a finer description of a state (which is a graph, instead of a set or a multiset), and for the possibility of specifying context-dependent operations (that is, operations which consume only some of the preconditions needed to apply them). In this paper we propose an event structure semantics for a class of graph grammars. Such semantics is able to show the correct maximum amount of concurrency and nondeterminism manifested by the behaviour of a graph grammar. The class considered is called safe, and contains all grammars whose productions are consumptive (i.e., they consume something), and whose generated graphs have no non-trivial automorphisms. The technique used to obtain the event structure is innovative and surprisingly simple, and consists of first defining a category of derivation traces for a given safe grammar (by exploiting a suitable independence relation), and then of applying a simple comma category construction to such category. The resulting comma category is shown to be the domain of finite configurations of a prime event structure. It is interesting to notice that our construction can be applied to safe Petri nets as well (which can be seen as a special case of safe grammars), yielding an event structure semantics equivalent to the classical one.

AN EVENT STRUCTURE SEMANTICS FOR SAFE GRAPH-GRAMMARS

CORRADINI, ANDREA;MONTANARI, UGO GIOVANNI ERASMO;
1994

Abstract

Graph grammars are the generalization of string grammars to graphs. Besides of generating graph languages, they can be used for the specification of concurrent and distributed systems. In this respect, they are far more expressive than, for example, Petri nets. In fact, they allow for a finer description of a state (which is a graph, instead of a set or a multiset), and for the possibility of specifying context-dependent operations (that is, operations which consume only some of the preconditions needed to apply them). In this paper we propose an event structure semantics for a class of graph grammars. Such semantics is able to show the correct maximum amount of concurrency and nondeterminism manifested by the behaviour of a graph grammar. The class considered is called safe, and contains all grammars whose productions are consumptive (i.e., they consume something), and whose generated graphs have no non-trivial automorphisms. The technique used to obtain the event structure is innovative and surprisingly simple, and consists of first defining a category of derivation traces for a given safe grammar (by exploiting a suitable independence relation), and then of applying a simple comma category construction to such category. The resulting comma category is shown to be the domain of finite configurations of a prime event structure. It is interesting to notice that our construction can be applied to safe Petri nets as well (which can be seen as a special case of safe grammars), yielding an event structure semantics equivalent to the classical one.
Corradini, Andrea; Ehrig, H; Lowe, M; Montanari, UGO GIOVANNI ERASMO; Rossi, F.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/29500
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 1
social impact