Colloquium on Petri Net Technologies
for Modelling Communication Based Systems
Berlin, October 21st-22nd, 1999
Andrea Corradini (University of Pisa):
On the process semantics of graph and net based systems
In the theory of Petri nets, an `occurrence net' is an acyclic, safe
net without forward and backward conflicts (i.e., a
place cannot be in the preconditions or in the postconditions of
more than one transition). A `non-sequential
process' of a P/T net N, as defined by Golz and Reisig [GR83],
consists of an occurrence net K together with a net morphism p: K - N
satisfying suitable conditions. Intuitively such a process records
a deterministic run of net N: a transition t of K records
one specific firing of transition p(t), while a place
s of K records the presence of a token on place p(s).
A non-deterministic generalization of such processes has been
introduced by Engelfriet [Eng91].
There are two appealing properties of non-sequential (deterministic)
processes. Firstly, a process represents a net computation in a
truly-concurrent way as a partial order, therefore more
abstractly than firing or step sequences (where a total ordering
is imposed). Actually, a process can be regarded as the
representative of the class of all firing (or step) sequences
that differ only for the order of non-causally related transition
firings. The second interesting aspect is that processes are
defined in terms of a suitable subclass of nets
and net morphisms. This homogeneity between systems (nets) and
their truly concurrent semantics (processes) is certainly very
convenient: On the one hand it confirms the suitability of nets
for the specification of concurrent aspects of computing; on the
other hand it makes the semantics immediately understandable to
anybody familiar with nets.
Graph Transformation Systems are a proper generalization of Petri nets,
and
various researchers have proposed suitable notions of processes for such
systems. In particular, in joint works with Paolo Baldan, Ugo Montanari
and
Francesca Rossi [CMR96,BCM98], the speaker introduced an original
definition of `graph process' which enjoys both of the above properties,
and related it to other concurrent semantics for graph transformation
systems.
In the talk I will introduce graph processes commenting on their
relationship with net processes, and I will summarize some recent
results
concerning the unfolding semantics of graph transformation systems and
non-deterministic graph processes.
[BCM98] P. Baldan, A. Corradini and U. Montanari, Concatenable graph
processes: relating processes and derivation traces, in Proceedings
ICALP'98, Lecture Notes in
Computer Science, Vol. 1443 (Springer, Berlin, 1998).
[CMR96] A. Corradini, U. Montanari, and F. Rossi, Graph Processes,
Fundamenta Informaticae, 26:241-265, 1996.
[Eng91] J. Engelfriet, Branching processes of Petri nets, Acta
Informatica,
28:575-591, 1991.
[GR83] U. Golz and W. Reisig, The Non-sequential Behaviour of Petri
Nets.
Info. and Co., 57:125-147, 1983.
Colloquium home page
