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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
