=Paper=
{{Paper
|id=None
|storemode=property
|title=Modelling Reaction Systems with Petri Nets
|pdfUrl=https://ceur-ws.org/Vol-724/paper4.pdf
|volume=Vol-724
}}
==Modelling Reaction Systems with Petri Nets==
https://ceur-ws.org/Vol-724/paper4.pdf
Proceedings of the 2nd International Workshop on Biological Processes & Petri Nets (BioPPN2011)
online: http://ceur-ws.org/Vol-724 pp.36-52
Modelling Rea tion Systems with Petri Nets
(Extended Abstra t)
Jetty Kleijn1 , Ma iej Koutny2 , and Grzegorz Rozenberg1,3
1
LIACS, Leiden University, 2300 RA, The Netherlands
2
S hool of Computing S ien e, New astle University, NE1 7RU, UK
3
Department of Computer S ien e, University of Colorado at Boulder
430 UCB Boulder, CO 80309-0430, U.S.A.
Abstra t. We investigate how Petri nets ould be used to provide a
faithful semanti s of rea tion systems, a formal framework for the inves-
tigation of pro esses arried by bio hemi al rea tions. We propose and
dis uss possible approa hes to this problem using some existing Petri
net lasses and on urren y on epts, su h as maximal parallelism. After
that we introdu e a new lass of Petri nets, alled set-nets, whi h provide
a omputational model mat hing very losely that exhibited by rea tion
systems. The key dieren e between standard Petri nets and set-nets
is that the former support multiset-based token arithmeti , whereas the
latter support set-based operations on tokens.
Keywords: rea tion system, Petri net, living ell, natural omputing,
set-net, model translation
1 Introdu tion
The investigation of the omputational nature of bio hemi al rea tions is a re-
sear h topi of Natural Computing. One of the goals of this resear h is to on-
tribute to a omputational understanding of the fun tioning of the living ell.
Rea tion systems [2, 3, 710℄ are a formal framework for the investigation of
pro esses arried out by bio hemi al rea tions in living ells. The entral idea
of this framework is that the fun tioning of a living ell is based on intera tions
between (a large number of) individual rea tions, and moreover these intera -
tions are regulated by two main me hanisms: fa ilitation/a eleration and inhi-
bition/retardation. These intera tions determine the dynami pro esses taking
pla e in living ells, and rea tion systems form a formal framework for developing
an abstra t theory of these pro esses.
The model of rea tion systems is based on prin iples remarkably dierent
from those underlying other existing models of omputation. The aim of this
paper is to develop a faithful Petri net model of rea tion systems. The main
motivation behind this is to establish whether Petri net based on epts (su h as
ausal pro esses) and methods (su h as synthesis of nets from a spe i ation of
their behaviour) ould be used to provide analyti al tools for rea tion systems.
It is not the intention of this paper to provide dire t feedba k to the area of
36
2 J.Kleijn, M.Koutny and G.Rozenberg
biologi al appli ations, but to establish bridges between biology and Petri nets
through the onne tion provided by rea tion systems.
As a rst step, we propose and dis uss four dierent approa hes to the mod-
eling of rea tion systems by using existing Petri net lasses and on urren y
on epts. However, as it turns out, in order to obtain a good mat h between re-
a tion systems and Petri nets, it is ne essary to re-evaluate one of the basi net
prin iples, namely, token ounting. This leads us to the introdu tion of a new
lass of Petri nets, alled set-nets, whi h provide a net based omputational
model mat hing very losely the omputations exhibited by rea tion systems.
The main dieren e between set-nets and standard Petri nets is that the latter
support multiset-based token arithmeti , whereas the former support set-based
(boolean) operations on tokens. Thus, the omputational `intuition' originating
from rea tion systems provides the inspiration to introdu e a new lass of nets
with intriguing and yet to dis over properties. Consequently, the main ontribu-
tion of this paper is more than just providing a bridge between rea tion systems
and the world of Petri nets. In the future, after fully understanding and master-
ing the properties of the new set-nets, one would hope to provide also a new
set of tools and analyses for biologi al appli ations.
The paper is organised in the following way. In the next se tion, we des ribe
basi notions of rea tion systems. Se tion 3 des ribes two methods of modelling
rea tion system using low-level Petri nets, and the next one does the same using
high-level Petri nets. The new lass of set-nets is introdu ed in Se tion 5, and
in Se tion 6 we explain why this new lass of nets an faithfully and elegantly
model rea tion systems. Comparison with related work is presented in Se tion 7.
Proofs of the results presented in this paper an be found in [16℄.
Notation We use the standard mathemati al notions and notation. A multiset
over a set X is a fun tion µ : X → N = {0, 1, 2, . . .}, and its support is ||µ|| =
{x ∈ X | µ(x) > 0}. The empty multiset ∅ satis es ||∅|| = ∅. A multiset may be
represented, somewhat informally, by listing its elements with repetitions, e.g.,
µ = {y, y, z} is su h that µ(y) = 2, µ(z) = 1, and µ(x) = 0 otherwise. We treat
sets as multisets without repetitions.
2 Rea tion systems
In this se tion, we explain some notions relevant to rea tion systems. It is our
intention to introdu e enough on epts to allow one to follow the subsequent
dis ussion on the relationship between rea tion systems and Petri nets. For a
omprehensive des ription of rea tion systems, in luding motivations, appli a-
tions and examples, the reader is referred to [79℄.
De nition 1 (rea tion system [79℄). A rea tion system is a pair: A =
(S, A), where S is a nite ba kground set omprising the entities of A, and A
is the set of rea tions of A. Ea h rea tion is a triplet of the form: a = (R, I, P ),
37
Modelling Rea tion Systems with Petri Nets 3
where the three omponents are nite non-empty sets: R ⊆ S is the set of rea -
tants, I ⊆ S is the set of inhibitors, and P ⊆ S is the set of produ ts.
The omponents of a rea tion a = (R, I, P ) are denoted by Ra , Ia and Pa ,
respe tively. De nition 1 des ribes the stati stru ture of a rea tion system. To
apture the dynami behaviour of rea tion systems, we need additional notions.
De nition 2 (state of rea tion system). A state of a rea tion system is
any set C of its entities. Then an initialised rea tion system is a triplet A =
(S, A, C0 ), where (S, A) is a rea tion system and C0 ⊆ S is the initial state.
In this and in the next se tion, we will onsider as a running example the
initialised rea tion system A0 = ({w, x, y, z}, {a, b, c}, {x, z}), with ba kground
set {w, x, y, z}, initial state {x, z}, and three rea tions:
a = ({x}, {y}, {y, z}) b = ({y}, {x}, {x, z}) c = ({z}, {w}, {z}) .
A rea tion system with ba kground set S has exa tly 2|S| potential states.
To des ribe possible transitions between these states, we need to say what is
meant by an o urren e of a rea tion or a set of rea tions.
De nition 3 (state hange). A rea tion a is enabled at a state C ⊆ S if
Ra ⊆ C and Ia ∩C = ∅; the result of a rea tion a at C is de ned by res a (C) = Pa
if a is enabled at C and res a (C) = ∅ otherwise. The result of A on C , denoted
by res A (C) onsists of the produ ts of all rea tions from A enabled at C, that is
[
res A (C) = res a (C) .
a∈A
This state hange is denoted by C −→ res A (C).
Note that the state Shanges aptured by De nition 3 are deterministi . More-
over, all entities in C \ a∈A res a (C) disappear. As a result, and unlike in other
formal models of dynami systems, there is no persisten y in a rea tion system
in the sense that an entity present in a state disappears unless it is sustained by
at least one rea tion.
For the example rea tion system A0 , we have:
{x, z} −→ {y, z} and {y, z} −→ {x, z} and {w, x, y} −→ ∅ .
One may observe that there is no on i t between rea tions in the ` lassi '
sense that the o urren e of one rea tion might imply that another rea tion
whi h is also enabled at the urrent state, annot o ur. This, again, is a feature
not found in most other formal models of dynami systems. In parti ular, it is
worthwhile to point expli itly to the `non- ounting' features of rea tion systems:
entities are either present or not, and produ ed or not, and rea tions an or
annot o ur based only on the presen e or absen e of ertain entities. There
is no representation of multiple instan es of entities or multiple o urren es of
38
4 J.Kleijn, M.Koutny and G.Rozenberg
rea tions. Thus rea tion systems are a qualitative rather than a quantitative
model.
We also note that there is an alternative notion of on i t-freeness for a set
of rea tions, alled onsisten y. A set of rea tions R is onsistent if for any two
rea tions a, b ∈ R, Ra ∩ Ib = Rb ∩ Ia = ∅. Clearly, if a set of rea tions is not
onsistent, then the rea tions it omprises annot be exe uted simultaneously.
Although the goal of this paper is a faithful `translation' of rea tion sys-
tems into Petri nets, we on lude this se tion with a number of omments about
resear h on rea tion systems. This resear h happens in the framework of re-
a tion systems where a rea tion system onstitutes the basi te hni al notion.
Depending on the goal of a spe i resear h theme, many other onstru ts are
introdu ed and studied (see, e.g., [2, 9, 10℄) they form various extensions of
the basi notion of rea tion system. For example, there are many biologi al situ-
ations where one needs to assign quantitative parameters (time, on entrations,
. . . ) to states of a bio hemi al system. Although rea tion systems are a qualita-
tive model (they annot ` ount'), they an be extended so that su h quantitative
parameters an be a ommodated. This is done through the use of measurement
fun tions whi h lead to rea tion systems with measurements (see [2, 3, 9, 10℄),
where various numeri al parameters an be assigned to ( al ulated for) onse -
utive states of dynami pro esses.
Finally, we want to point out that (be ause living ells are open systems)
rea tion systems have an environment and they operate/evolve within a hanging
ontext (with entities oming from the environment in uen ing the transitions
of dynami pro esses). In this paper, however, we will onsider only ontext-
independent pro esses de ned by a rea tion system with an initial state, where
ea h next state is obtained solely as the result of rea tions taking pla e in the
previous state (thus assuming that the environment does not in uen e state
transitions).
3 Rea tion systems and low-level Petri nets
In this se tion, we dis uss two possible ways of modelling ontext-independent
pro esses of rea tion systems using low-level Petri nets (pt-nets extended with
with inhibitor and a tivator ar s).
In addition to the standard notions of rea tion systems, in order to better
explain how they relate to Petri nets, throughout the rest of this paper we will
say that a set R ⊆ A is enabled at C if ea h rea tion of R is enabled at C . If
R ⊆ A is enabled at C , then
R
[
C =⇒ res R (C) = Pa .
a∈R
denotes the ee t of R at C .
De nition 4 (pt-nets with inhibitor and a tivator ar s [14℄). A pt-net
with inhibitor and a tivator ar s (or ptia-net) N = (Pl , Tr , Flw , Inh, Act, M0 )
39
Modelling Rea tion Systems with Petri Nets 5
is a tuple su h that Pl and Tr are nite, disjoint sets of respe tively pla es and
transitions, and: Flw ⊆ (Pl × Tr ) ∪ (Tr × Pl ), Inh ⊆ Pl × Tr , Act ⊆ Pl × Tr
are respe tively the sets of ow, inhibitor and a tivator ar s. Moreover, M0 is
a multiset of pla es, the initial marking of N ; in general, any multiset of pla es
is alled a marking.
In diagrams, pla es are drawn as ir les and transitions as re tangles. Mark-
ings are the possible global on gurations (states) of N . We say that a pla e q
is marked under a marking M if M (q) > 0, where M (q) denotes the number
of o urren es of q in M . In diagrams, markings are indi ated by putting M (q)
tokens inside the ir le representing q. If (x, y) ∈ Flw , then (x, y) is an ar lead-
ing from node x to node y . A double headed arrow between q and t indi ates
that (q, t), (t, q) ∈ Flw . An inhibitor ar ends with a small open ir le, while an
a tivator ar ends with a small bla k ir le.
Given a node x, we denote by • x the set of input nodes of x, i.e., those y
for whi h (y, x) ∈ Flw , and by x• the set of output nodes of x, i.e., those y
for whi h (x, y) ∈ Flw . For a transition t we use: ◦ t = {q | (q, t) ∈ Inh} and
t = {q | (q, t) ∈ Act} to denote the inhibitor and a tivator pla es of t. All four
notations extend in the usual way to sets of nodes. As in the ase of rea tion
systems, we now formalise the notion of marking (state) hange.
De nition 5 (marking hange). A multiset of transitions U (also alled a
step) is enabled P at a marking M if ◦ U ∩ ||M || = ∅, U ⊆ ||M || and, for every
pla e q, M (q) ≥ t∈q• U (t) (re all that ||M || is the set of q whi h o ur in M ,
and U (t) is the number of o urren es of t in U ).
In su h a ase, U an be red with its ee t on M being given P by the result-
ing marking M ′
su h that, for every pla e q : M ′
(q) = M (q) − t∈q• U (t) +
t∈• q U (t). We denote this by M [U iM . Moreover, if U is a maximal (w.r.t.
′
P
multiset in lusion) step of transitions enabled at M , then we may denote this
marking hange also by M [U imax M ′ .
Note that whenever a step U is enabled at marking M it must be the ase
that all a tivator pla es of transitions in ||U || are marked (are in ||M ||) and none
of the inhibitor pla es of transitions in ||U || are marked.
We now make some general observations and assumptions about the rela-
tionship between rea tion systems and nets.
Entities an be represented by pla es, and rea tions by net transitions.
Sin e there are no on i ts between rea tions, a tivator ar s an be used
to test for the presen e of rea tants (rather than laiming resour es for the
ex lusive use as with ordinary ar s and input pla es).
All rea tions that an o ur in a rea tion system do o ur, and the only en-
tities left after a state hange are the newly generated produ ts. In the Petri
net framework, these features orrespond to maximal parallelism des ribed
at the end of De nition 5, and pla e resetting [6℄ des ribed later on.
40
6 J.Kleijn, M.Koutny and G.Rozenberg
x x
rx
qa
a a
y ⋆ y
ry
qb ⋆
b r b
z ⋆ z
NI (A0 ) rz NII (A0 )
qc ⋆
c c
w w
(a) rw (b)
Fig. 1. Method I and II representations of the rea tion system A0 .
Method I. The rst attempt is illustrated in Figure 1(a) for the example rea -
tion system A0 . Method I produ es a ptia-net NI (A0 ) su h that:
Transitions a, b and c use a tivator ar s and inhibitor ar s to test respe tively
for the presen e and absen e of tokens in the pla es w, x, y and z .
Pla es qa , qb and qc ensure that the three transitions modelling rea tions,
i.e., a, b and c, re at most on e in any step. This orresponds to the `non-
ounting' of o urren e instan es of the same rea tion in a rea tion system.
Transitions rw , rx , ry and rz (in a maximal step) empty the four pla es
modelling entities w, x, y and z . This does not have any in uen e on the
ring of the transitions a, b and c.
In a single maximal step, M [U imax M ′ , the net res a maximal multiset of
transitions U enabled at marking M and then produ es a new marking M ′ .
For the net in Figure 1(a), su h a ring rule gives:
{x, z, qa , qb , qc } [{rx , rz , a, c}imax {y, z, z, qa, qb , qc }
{x, x, x, z, qa , qb , qc } [{rx , rx , rx , rz , a, c}imax {y, z, z, qa, qb , qc } .
Formally, given an initialised rea tion system A = (S, A), Method I yields
a ptia-net NI (A) su h that the pla es, transitions and the initial marking are,
respe tively: Pl = {qa | a ∈ A} ∪ S , Tr = {rs | s ∈ S} ∪ A and M0 = {qa | a ∈
A}+C0 . Moreover, the sets of ow, inhibitor and a tivator ar s are, respe tively:
Flw = {(s, rs ) | s ∈ S} ∪ {(a, qa ), (qa , a) | a ∈ A} ∪ {(a, s) | a ∈ A ∧ s ∈ Pa }
Inh = {(s, a) | a ∈ A ∧ s ∈ Ia } Act = {(s, a) | a ∈ A ∧ s ∈ Ra } .
Note that this kind of modelling in ombination with the `resetting' of pla es
w, x, y and z in ea h red step, implemented by the auxiliary transitions rw ,
rx , ry and rz , means that the resulting Petri net is bounded (in every rea hable
marking the multipli ity of ea h pla e is never more than the number of rea tions
of A if A has at least one rea tion).
In order to relate the behaviour of the original rea tion system A and its
ptia-net representation NI (A) just introdu ed, we need two mappings. The rst
41
Modelling Rea tion Systems with Petri Nets 7
one takes a marking M of NI (A) and returns a state of A, and the other takes
a step U of transitions of NI (A) and returns a set of rea tions of A, as follows
νI (M ) = S ∩ ||M || and ϕI (U ) = A ∩ ||U ||. It is then possible to show a number
of results, where a marking M of the ptia-net NI (A) is alled well-formed if
M (qa ) = 1, for every a ∈ A.
First, M0 is a well-formed marking satisfying ν(M0 ) = C0 , and if M is a
well-formed marking and M [U iM ′ , then M ′ is also well-formed. Se ond, if M is
a well-formed marking, then for every rea tion a ∈ A, a is enabled at M i {a}
is enabled at state νI (M ). We then an show that the translation is sound.
Theorem 1. If M is a well-formed marking then:
ϕ (U)
1. M [U iM ′ implies νI (M ) =⇒
I
νI (M ′ ). Moreover, if M [U imax M ′ , then ϕI (U )
omprises all rea tions enabled at νI (M ).
2. νI (M ) =⇒
R
C implies M [U iM ′ for some U and M ′ satisfying: ϕI (U ) = R
and νI (M ) = C . Moreover, if R omprises all rea tions enabled at νI (M ),
′
then M [U imax M ′ .
Thus, ea h maximal omputational step in the Petri net orresponds to a
unique exe ution of the rea tion system, and ea h exe ution in the rea tion
system orresponds to at least one maximal step in the Petri net. For example,
the two exe utions given above for the Petri net in Figure 1(a) both orrespond
{a,c}
to {x, z} =⇒ {y, z} in the rea tion system A0 .
Note that in Figure 1(a) one annot simply delete the auxiliary pla es of the
form qr as then ea h of the transitions representing rea tions ould be unbound-
edly enabled. To address this problem one ould hange the a tivator ar s from
pla es representing entities into ow ar s. Then, however, it would be ne essary
to add weights |R| to the ar s orresponding to the produ tion of new entities
in order to avoid on i ts on the pla es representing the rea tants.
Method II. The rst attempt to model ontext-independent rea tion systems
provides a sound translation, but it is not simple as it employs features whi h
an make formal analysis and veri ation far from easy. One way of improving
Method I ould be to repla e multisets of red transitions by sets of red tran-
sitions leading to a maximal set-semanti s. This an be a hieved by using reset
ar s [6℄, onne ting pla es to transitions and indi ated by ⋆'s in the diagrams,
whi h always empty their sour e pla e. Formally, reset ar s Reset ⊆ Pl × Tr do
not have any in uen e on the enabledness of a step U , but the al ulation of the
marking of a pla e q after the ring of U (now a set) at marking M hanges to:
M (q) − |q • ∩ U | + |• q ∩ U | if ({q} × U ) ∩ Reset = ∅
M ′ (q) = •
| q ∩ U| otherwise .
The resulting ptia-net with reset ar s NII (A0 ) is shown in Figure 1(b). Tran-
sition r is always enabled and, when red, removes all the tokens from the
pla es modelling the entities. For the net in Figure 1(b), the new ring rule gives
42
8 J.Kleijn, M.Koutny and G.Rozenberg
{x, z} [{r, a, c}imax {y, z, z} and {x, x, x, z} [{r, a, c}imax {y, z, z}. One an then
show that a ounterpart of Theorem 1 holds also in this ase, with νII de ned as
νI before and ϕII (U ) = U \ {r}. As transition r is always enabled, we now have a
one-to-one orresponden e between groups of exe uted rea tions and transitions,
at the pri e of introdu ing non-standard reset ar s.
To remove the need to have reset ar s or, equivalently, to obtain a one-to-
one orresponden e between states and markings, one ould hange the rules for
inserting tokens into pla es, by basi ally applying an OR-treatment for arriving
tokens. This would, of ourse, be a radi al departure from the standard Petri
net approa h, but one worth investigating. The resulting model of set-nets will
be des ribed in Se tion 5.
4 Rea tion systems and high-level Petri nets
The two translations des ribed in the previous se tion use low-level pt-nets ex-
tended with reset ar s in addition to inhibitor and a tivator ar s as well as
maximal parallelism. Reset ar s are a non-standard me hanism and, in parti u-
lar, they do not as yet support a ausal pro ess semanti s. Moreover, the ee t of
a reset ar depends on the urrent marking rather than on a xed input/output
relation with its neighbourhood. To ope with this problem, we will now outline
two translations from ontext-independent rea tion systems to high-level Petri
nets. We assume familiarity with the basi on epts of high-level nets [13℄, in
parti ular, ar ins riptions, a tivator and inhibitor ar s, and simple transition
guards.
Method III. The rst translation is illustrated by the high-level net NIII (A0 )
shown in Figure 2(a). In this ase, tokens are positive integers a ting as though
they were time-stamps. Intuitively, a token n is a tive only in the n-th exe ution
y le of the rea tion system. Be ause the same token annot be a essed more
than on e in a step sequen e evolution, reset ar s are not needed anymore. Sin e
the X transition res in ea h maximal step, the y le number n held in the
` lo k' pla e clk is known to all transitions representing rea tions. In the pla es
representing entities, they he k only for tokens n, ignoring all the other tokens
produ ed in previous y les, and then produ e tokens with value n+1 to be used
in the next y le. The initial marking M0 is formed by inserting a single token 1
into pla e clk and all the pla es s su h that s ∈ C0 . Note that the resulting net
may be unbounded as the tokens in pla es representing entities are not `garbage
olle ted'. For the high-level net NIII (A0 ) in Figure 2(b), we have:
{x 7→ {1}, y 7→ ∅, z 7→ {1}, w 7→ ∅, clk 7→ {1}}
[{an7→1 , cn7→1 , Xn7→1 }imax
{x 7→ {1}, y 7→ {2}, z 7→ {1, 2, 2}, w 7→ ∅, clk 7→ {2}}
[{bn7→2 , cn7→2 , Xn7→2 }imax
{x 7→ {1, 3}, y 7→ {2}, z 7→ {1, 2, 2, 3, 3}, w 7→ ∅, clk 7→ {3}} .
43
Modelling Rea tion Systems with Petri Nets 9
x x ay
1 1 n
n+1
n+1
a a clk a 1
y n
y n
n
clk 1 X n+1
n+1 n+1 ax hm ≥ ni
b b clk b 1
z z n
m
1 1
n+1
c c clk c 1
w w n
(a) NIII (A0 ) (b) NIV (A0 )
Fig. 2. Method III and IV representations of rea tion system A0 . Note that n and
m are net variables, and that to avoid lutter not all ar s have been annotated: all
the ow (thi ker) ar s to pla es x, y , z are in fa t annotated with n + 1, and all the
unannotated inhibitor and a tivator ar s are annotated with n. In (b), the auxiliary
pla es for transitions b and c are omitted. Note that hm ≥ ni is the guard of transition
ax , and all other transitions have the trivial true guard.
As in the ase of Method I, not every marking M of NIII (A) an represent a
valid state of the rea tion system A. We say that M is lo k- onsistent if there
is a single token k in pla e clk , and all the tokens l in other pla es satisfy l ≤ k .
Relating the resulting net and the original rea tion system an be done using
the following two mappings: νIII (M ) = {s ∈ S | ||M (clk )|| ∩ ||M (s)|| 6= ∅}
and ϕIII (U ) = U \ {X}. One an show that M0 is a lo k- onsistent marking
satisfying ν(M0 ) = C0 , and if M is a lo k- onsistent marking and M [U imax M ′
then M ′ is also lo k- onsistent.
Theorem 2. If M is a lo k- onsistent marking then:
(U)
1. M [U imax M ′ implies νIII (M ) =⇒ νIII (M ′ ).
IIIϕ
2. νIII (M ) =⇒
R
C implies M [U imax M ′ for some U and M ′ satisfying: ϕIII (U ) =
R and νIII (M ′ ) = C .
Method IV. In the se ond high-level net onstru tion the aim is to eliminate
the need for maximal parallelism using information present in the time-stamped
tokens. We repla e the global clk pla e by individual clk a pla es, whi h are in re-
mented by transitions a representing rea tions. Moreover, whenever a is blo ked
from ring in a ertain y le one of the auxiliary transitions orresponding to
the possible `reasons' for the blo king a is red to in rement the token in clk a .
This results in an in rement of the y le number for this transition (in ase
44
10 J.Kleijn, M.Koutny and G.Rozenberg
there is more than one reason for blo king, an auxiliary transition is hosen
non-deterministi ally).
There are two possible reasons why a might be blo ked in y le n. One is the
presen e of a token n in the pla e representing an inhibitor of a, and to he k for
this we use a transition with an a tivator ar , e.g., ay in Figure 2(b). The other is
more ompli ated as it is a la k of token n in the pla e representing a rea tant s
for a, and to he k for this we use a transition with an inhibitor ar . However, we
also need to ensure that all transitions whi h feed tokens to s have already had
a han e to do so, and we he k this using extra a tivator ar s together with a
transition guard whi h evaluates to true if all su h feeding transitions have their
lo al y le su iently high, e.g., transition ax in Figure 2(b). The overall result
for the rea tion system A0 is a high-level net NIV (A0 ) shown in Figure 2(b).
The resulting high-level net is exe uted a ording to the standard sequential
(interleaving) ring rule and its behaviour losely simulates that of the net ob-
tained by Method III, and so also the behaviour of the original rea tion system.
We skip the full des ription of the relationship between these two nets. Intu-
itively, a marking M of the se ond translation orresponds dire tly to a marking
of the rst one if all the pla es of the form clk a ontain the same single token
k , and all the tokens l in other pla es satisfy l ≤ k . (Note that from ea h rea h-
able marking of the se ond translation one an exe ute a sequen e of transitions
leading to a marking with this property.)
5 Set-nets
In our attempts to obtain a dire t and elegant translation from rea tion systems
into Petri nets, a major and as far as we an tell insurmountable problem was
the fa t that several transitions may insert tokens into a pla e representing
the presen e of a single entity. In this se tion, we introdu e set-nets, a model
that resulted from loser investigations into the possibilities of an OR-treatment
of arriving tokens representing the produ tion of entities by rea tions. Note
that OR-treatment of ausality has been onsidered in [20℄, but the underlying
prin iple there was ompletely dierent from what we are going to propose.
The main idea is that in a set-net there is no on ept of ounting. Pla es
are marked or not marked and ar s have no weights. Set-nets resemble elemen-
tary net systems (en-systems) [19℄ whi h is a fundamental model to study basi
features of on urrent systems, in luding on i t, ausality and independen e.
However, their exe ution semanti s is dierent. In set-nets, a marked pla e in-
di ates the presen e of a resour e without any quanti ation. Hen e any number
of transitions that take input from this pla e an be red at the same time.
Moreover, ring a transition empties all its input pla es. Thus there are no on-
i ts over tokens in set-nets, unlike in en-systems or pt-nets. Similarly, pla es
do not ount the tokens, and the ring of a transition simply marks ea h of its
output pla es (whether or not they were already marked). We will build up the
new model in two stages, introdu ing rst set-nets with only ow ar s.
45
Modelling Rea tion Systems with Petri Nets 11
r↓
r↓ a r a r
r
q b q b q
q↓ b
q q↓ q↓
s↓ (a) s s↓ (b)
s
Fig. 3. A set-net representing rea tion system A1 (a); and an o urren e net on-
stru ted for its step sequen e {b, q↓ , s↓ }{a, b, r↓ , q↓ } (b) .
De nition 6 (basi set-net). A tuple SN = (Pl , Tr , Flw , M0 ) is a (basi )
set-net if the rst three omponents are as in De nition 4, and M0 ⊆ Pl is the
initial marking (in general, any set of pla es is a marking).
The graphi al representation of set-nets is the same as in the ase of Petri
nets. We now formalise the ring rule for set-nets.
De nition 7 (marking hange). A set of transitions U (also alled a step)
is enabled at a marking M if • U ⊆ M . In su h a ase, U an be red with its
ee t on M being given by the resulting marking M ′ = (M \ • U )∪U • . We denote
this by M [U iM ′ . Moreover, if U is the set of all transitions enabled at M (i.e.,
all transitions t satisfying • t ⊆ M ), then we may write M [U imax M ′ .
Hen e a step U enabled at a marking M may ontain two distin t transitions
t and u for whi h • t ∩ • u 6= ∅ or t• ∩ u• 6= ∅ and yet the ommon pla es will
never ontain more than one token. Sin e tokens are manipulated using set-based
arithmeti we have hosen the name `set-nets' for the new lass of Petri nets.
We have introdu ed rst basi set-nets (without inhibitor and a tivator
ar s), as it seems that one an attempt to develop for them a ounterpart of
`stru ture theory' of pt-nets. To illustrate our point, let us onsider a basi set-
net SN = (Pl , Tr , Flw , M0 ) with at least one transition. A non-empty set of
pla es Sphn ⊆ Pl is alled a siphon if • Sphn ⊆ Sphn • . Similarly, a non-empty
set of pla es Trap ⊆ Pl is alled a trap if Trap • ⊆ • Trap . It an be easily seen
that an empty siphon annot a quire a token by ring any transition, and a
marked trap annot be ome empty by ring any transition. Both type of sets
of pla es an be used to provide a su ient ondition for deadlo k-freeness in
pt-nets whi h was a major motivation behind the development of their stru ture
theory. As it turns out, the same an be done in ase of set-nets.
Theorem 3. If in the initial marking, every siphon ontains a marked trap,
then the set-net is deadlo k free.
We next introdu e set-nets with inhibitor and a tivator ar s.
46
12 J.Kleijn, M.Koutny and G.Rozenberg
De nition 8 (set-net). A tuple SNIA = (Pl , Tr, Flw , Inh, Act, M0 ) is a set-
net if the rst ve omponents are as in De nition 4, and the last one as in
De nition 6.
The de nitions and notations on erning the marking hange in SNIA are the
same as for SN in De nition 7 with one ex eption, namely a set of transitions U
is enabled at a marking M if • U ∪ U ⊆ M and ◦ U ∩ M = ∅. It is interesting to
observe that an enabled step U is always onsistent in the sense that (• U ∪ U )∩
◦
U = ∅. Su h a property has a natural and dire t (as we will see) onne tion
with the notion of onsisten y introdu ed for rea tion systems.
As before, given a transition t representing a rea tion, the sets • t, ◦ t and t
orrespond to the rea tants, inhibitors and produ ts of this rea tion. However,
we do not require that these sets be non-empty in a set-net (at least at this
point) as su h an assumption is not ne essary.
6 Rea tion systems and set-nets
Rea tion systems and set-nets t together well in the sense that both do not
ount tokens and both hange states on the basis of the presen e/absen e of
resour es, represented by sets. Moreover, under the set-net semanti s, ordinary
ar s (transitions) an be used to empty pla es. In this semanti s, reset ar s with
their ee t depending on the urrent number of tokens in a pla e are meaningless.
Finally, following the assumption that all rea tions that an take pla e do take
pla e, the maximal set-semanti s an be employed.
Figure 3(a) depi ts a set-net orresponding to a ontext-independent ini-
tialised rea tion system A1 = ({r, q, s}, {a, b}, {q, s}), where a = ({r, q}, ∅, {r})
and b = ({q}, ∅, {r, q}). (For reasons of larity, we allow in this se tion rea tions
without any inhibitors.) As before, pla es represent entities. Transitions r↓ , q↓
and s↓ ensure that on e the set-net is a tive only tokens produ ed in the last
maximal step are present in the urrent marking. For example, we have:
{q, s} [{b, q↓, s↓ }imax {r, q} [{a, b, r↓, q↓ }imax {r, q} ,
and so σ = {b, q↓ , s↓ }{a, b, r↓, q↓ } is a max-step sequen e. Relating the behaviour
of the set-net model and the original rea tion system is easy and we obtain a
ounterpart of Theorem 1 with ν(M ) = M and ν(U ) = U \ {s↓ | s ∈ S}.
For a set-net without inhibitor and a tivator ar s as in Figure 3(a), one
an investigate the ausality semanti s of rea tion systems based on the un-
foldings of the orresponding set-nets. Figure 3(b) shows how su h an o ur-
ren e net ould be derived for the set-net in Figure 3(a) and its step sequen e
{b, q↓ , s↓ }{a, b, r↓ , q↓ } whi h orresponds of the state sequen e {b}{a, b} of the
original rea tion system. It is worth observing that the pro ess has bran hing
pla es whi h is not possible, in the ase of pro esses of en-systems or pt-nets.
This, however, is fully onsistent with the exe ution semanti s of set-nets.
47
Modelling Rea tion Systems with Petri Nets 13
Modelling inhibition aspe ts of rea tions is rather straightforward using in-
hibitor ar s, as illustrated by the set-net in Figure 4(a), representing the ontext-
independent initialised rea tion system A2 = ({r, q, s}, {a, b}, {q}), where:
a = ({r, q}, ∅, {r}) and b = ({q}, {s}, {r, q}) and c = ({q}, ∅, {s}) .
Using inhibitor ar s gives a ompa t translation of rea tion systems whi h is
in a sense minimal w.r.t. the number of pla es, ar s and transitions. Moreover,
relating the behaviour of the resulting set-nets and the original rea tion systems
an be done as before. Formally, the pla es, transitions and initial marking of
the translation are given by: Pl = S , Tr = A ∪ {s↓ | s ∈ S} and M0 = C0 . There
are no a tivator ar s, and the ow and inhibitor ar s are as follows:
Flw = {(s, s↓ ) | s ∈ S} ∪ {(s, a) | a ∈ A ∧ s ∈ Ra } ∪ {(a, s) | a ∈ A ∧ s ∈ Pa }
Inh = {(s, a) | a ∈ A ∧ s ∈ Ia } .
The development of a ausal pro ess semanti s of set-nets with inhibitor ar s is
more di ult. It is therefore interesting to onsider models of rea tion systems
using set-nets without any inhibitor ar s, as outlined next.
Figure 4(b) shows a set-net without inhibitor ar s modelling A2 . The way in
whi h it does it is now more involved. More pre isely, ea h exe ution step of the
rea tion system is simulated in two phases by the set-net operating a ording to
the maximal parallelism exe ution semanti s. To keep these two phases learly
separated, they are ontrolled by an additional y li subnet with two pla es. The
key aspe t of the onstru tion is the use of a ` omplement' scpl of the `regular'
pla e s whi h at the time of he king whether s is empty by rea tion b ontains
a token i s is empty.
Figure 4(c) provides a generi pi ture of how, in the proposed onstru tion,
a set-net (without inhibitor ar s) handles an entity r in its role as a rea tant,
inhibitor, and produ t. Note that r is represented by two pla es, r and rcpl , and
if rcpl is marked then the entity r in absent in the urrent state. Moreover, ea h
rea tion d is represented by two transitions, d and d′ . The rst orresponds to
the enabling stage of d, and the se ond to the generation of its produ ts.
The rst phase of the simulation always starts in a onsistent marking M
in whi h there is a token in pla e phI ; for every s ∈ S , s ∈ M ⇔ scpl ∈ / M,
and otherwise all pla es are empty. In this phase transitions orresponding to
rea tions be ome a tive on the basis of the presen e and absen e of their rea -
tants and inhibitors. Simultaneously, transitions of the form r↓ and r↑ take are
that all the entities present in the urrent state ease to exist (their orrespond-
ing pla es are emptied and the omplement pla es lled). In the se ond phase,
ea h enabled transition d′ nishes the exe ution of the orresponding rea tion,
and marks the pla es orresponding to the entities produ ed by rea tion d and
empties their omplements.
Relating the behaviour of the set-net model and the original rea tion system
is more ompli ated, using the following two mappings:
ν(M ) = M \({phI }∪{scpl | s ∈ S}) ϕ(U ) = U \({I}∪{s↓ | s ∈ S}∪{s↑ | s ∈ S}) .
48
14 J.Kleijn, M.Koutny and G.Rozenberg
r↓ a a′
r
r↓ a
r II q↓ b b′
q
q↓ b phII phI
q s↓ c c′
I s
s↓ c
s s↑
(a) (b)
scpl
r
r↓ a a′
b b′
r cpl
r↑ c c′ (c)
Fig. 4. Two set-nets representing A2 (a, b). Generi translation without inhibitor ar s:
here r is a rea tant for rea tion a, produ t for b, and inhibitor for c (c). Note that not
all pla es and ar s are shown; in parti ular, ea h rea tion has at least one rea tant and
hen e transitions like c an only re in the rst phase.
One an then show that M0 is onsistent and satisfying ν(M0 ) = C0 , and if M
is a onsistent marking and M [U imax M ′′ [U ′ imax M ′ then M ′ is also onsistent.
Theorem 4. If M is a onsistent marking then:
1. M [U iM ′′ [U ′ iM ′ implies ν(M ) =⇒ ν(M ′ ).
ϕ(U)
2. ν(M ) =⇒
R
C implies M [U iM ′′ [U ′ iM ′ for some U , U ′ , M ′ and M ′′ satisfy-
ing: ϕ(U ) = R and ν(M ′ ) = C
7 Related work and on luding remarks
When introdu ing a new lass of Petri nets, espe ially a fundamental one, it is
ne essary to put it in the ontext of existing formalisations. To make omparison
fair, we will now drop the assumption about maximal parallelism in the exe ution
of set-nets (whi h is implied by the exe ution mode of rea tion systems), and
onsider semanti s whi h allows any set of enabled transitions to be red.
Set-nets are so simple when it omes to their de nition, that it is reasonable
to expe t that there were in the past net lasses with similar features. Indeed, the
fundamental lass of en-systems [19℄ extended with inhibitor as well as a tivator
ar s [12, 17, 18℄ basi ally have the same stati stru ture as set-nets. However,
their treatment of on i ts between transitions a essing the same token, as
well blo king a transition whi h ould add a token to a marked pla e, are totally
49
Modelling Rea tion Systems with Petri Nets 15
a b q0 b0 q1
q
a0
(a) c (b) c a1 b1
Fig. 5. Boolean net ( set-net with sequential semanti s) (a), and 1-safe pt-net simu-
lating its (sequential) behaviour (b).
dierent. The latter issue has been noted in the past, and the onstraint relaxed.
For example, there are variations of Petri nets, su h as Boolean Petri nets, where
adding a token to an already marked pla e does not add another token [4, 5, 11℄.
Also, behaviour of this kind was mentioned in [1℄ in the ontext of net synthesis.
Having said that, the semanti s onsidered in prior works known to us was
based on single transition rings, rather than (maximal) steps as is the ase
for set-nets. Therefore, the previous models were not on erned with multiple
inputs of tokens to a single pla e something whi h is essential if one wants to
faithfully model rea tion systems. Furthermore, by aiming at a set-semanti s,
we had to introdu e the non- on i t feature on the ow ar s onsuming the
tokens. Therefore, as far as we are aware, the model of set-nets is an original
ontribution to the eld of Petri nets.
As we already mentioned, set-nets with interleaving semanti s are nothing
but Boolean nets used, for instan e, in [5℄. In su h a ase, the la k of on i t
when ring two transitions sharing an input pla e is an irrelevant issue, and the
only non-standard aspe ts is that ring a transition with a marked output pla e
does not in rease the token ount in that pla e. Su h a feature, moreover, an
easily be modelled using ordinary 1-safe pt-nets, a ording to the following idea.
First, one splits ea h pla e q into pla es q 0 and q 1 , respe tively representing
the la k and presen e of a token in q . Then, ea h transition t adding tokens
to pla e q is split into t0 and t1 to a ount for two dierent states the pla e
q an be in represented by q 0 and q 1 . Figure 5 illustrates this onstru tion.
It an be easily seen that both nets generate the same sequential rea hability
graphs assuming that a0 and a1 are instan es of a, and b0 and b1 are instan es
of a. However, on e we start treating the net in Figure 5(a) as set-net, the
situation hanges radi ally. The reason is that we then have three rings of
the following form: ∅[{a}i{q}, ∅[{b}i{q} and ∅[{a, b}i{q}. Now, the standard
lasses of Petri nets enjoy the so- alled subset property whi h means that if a
step U is enabled at marking M , then also any of its subsets is enabled as well.
Suppose, then, that there is a Petri net N satisfying this property and su h that
its step rea hability graph is the same as that of the set-net in Figure 5(a),
perhaps after renaming λ being applied to the transitions of the former. Then
we have to have two transitions, t and u, in N su h that λ(t) = a, λ(u) = b and
M0 [{t, u}iM . Then, by the subset losure property, we also have M0 [{t}iM ′
and M0 [{u}iM ′′ . Hen e, by the rea hability graph isomorphism, we must have
50
16 J.Kleijn, M.Koutny and G.Rozenberg
M = M ′ = M ′′ as well as M0 6= M . Hen e we have: M0 [{t, u}iM and M0 [{t}iM
and M0 [{u}iM and M0 6= M . In the standard Petri nets, in luding various
extensions of pt-nets, M0 [{t, u}iM and M0 [{t}iM would imply that u does not
hange the urrent marking. Similarly, M0 [{t, u}iM and M0 [{u}iM would imply
that t does not hange the urrent marking. Yet the simultaneous ring of t and
u does hange the marking as M0 6= M . This would produ e a ontradi tion.
What we just presented is intuition rather than proof, however, we expe t that
detailed arguments an be developed for any of the standard net lasses. An
important onsequen e, however, is that set-nets are semanti ally dierent from
the existing net lasses and therefore deserve to be re ognised as an original
ontribution.
8 Con lusions
The main initial motivation of our investigation was to see how Petri net based
on epts ould be deployed to analyse rea tion systems. In parti ular, we wanted
to dis over methods for he king properties of rea tion systems by relating them
to the properties of the orresponding Petri nets and ausal pro esses.
We proposed modelling methods resulting both in low-level and high-level
nets. In all four ases, we established a lose orresponden e between the mark-
ings of Petri nets and states of the original rea tion systems. The same was true
of the evolutions of two orresponding models. In fa t, we established that they
have essentially isomorphi state spa es. All these net models, however, exhibited
de ien ies w.r.t. simpli ity and/or elegan e and/or tra tability of the transla-
tion. For example, both high-level net models are intrinsi ally unbounded, and
the se ond of the low-level translations uses reset ar s. We therefore proposed
a new lass of Petri nets, alled set-nets, whi h we feel provide a strong mat h
with the rea tion systems and their semanti s.
In this way we think we derived new interesting notions and ontributions to
Petri net theory based on our experien es with rea tion systems in a similar way
as the on epts of lo alities and lo ally maximal on urren y were derived from
our previous investigation of a Petri net semanti s of membrane systems [15℄.
A knowledgement We would like to thank the anonymous reviewers for their
suggestions and omments. This resear h was supported by the Pas al Chair
award from Leiden University and the Epsr Verdad proje t.
Referen es
1. E.Badouel and P.Darondeau: Theory of regions. Le ture Notes in Computer S ien e
1491 (1998) 529586
2. R.Brijder, A.Ehrenfeu ht, M.G.Main and G.Rozenberg: Rea tion systems with du-
ration. Le ture Notes in Computer S ien e 6610 (2011) 191202
3. R.Brijder, A.Ehrenfeu ht, M.G.Main and G.Rozenberg: A Tour of Rea tion Sys-
tems. Int. Journal of Foundations of Computer S ien e (2011)
51
Modelling Rea tion Systems with Petri Nets 17
4. L.Czaja: A Cal ulus of Nets. Cyberneti s and Systems Analysis 29 (1993) 185-193
5. P.De Bra, G.J.Houben and Y.Kornatzky: A Formal Approa h to Analyzing the
Browsing Semanti s of Hypertext. Pro . CSN-94 Conferen e (1994) 7889
6. C.Dufourd, A.Finkel, and Ph.S hnoebelen: Reset Nets Between De idability and
Unde idability Le ture Notes in Computer S ien e 1443 (1998) 103-115
7. A.Ehrenfeu ht, M.Main and G.Rozenberg: Combinatori s of Life and Death for
Rea tion Systems. Int. J. of Foundations of Computer S ien e 22 (2009) 345356
8. A.Ehrenfeu ht and G.Rozenberg: Rea tion Systems. Fundamenta Informati ae 76
(2006) 118
9. A.Ehrenfeu ht and G.Rozenberg: Events and Modules in Rea tion Systems. The-
oreti al Computer S ien e 376 (2007) 316
10. A.Ehrenfeu ht and G.Rozenberg: Introdu ing Time in Rea tion Systems. Theoret-
i al Computer S ien e 410 (2009) 310322
11. M.Heiner, D.Gilbert and R.Donaldson: Petri Nets for Systems and Syntheti Bi-
ology. Le ture Notes in Computer S ien e 5016 (2008) 215264
12. R.Jani ki and M.Koutny: Semanti s of Inhibitor Nets. Information and Computa-
tion 123 (1995) 116
13. K.Jensen: Coloured Petri Nets and the Invariant-Method. Theoreti al Compututer
S ien e 14 (1981) 317-336
14. J.Kleijn and M.Koutny: Pro esses of Petri Nets with Range Testing. Fundamenta
Informati ae 80 (2007) 199219
15. J.Kleijn, M.Koutny and G.Rozenberg: Pro ess Semanti s for Membrane Systems.
Journal of Automata, Languages and Combinatori s 11 (2006) 321340
16. J.Kleijn, M.Koutny and G.Rozenberg: Modelling Rea tion Systems with Petri
Nets. Te hni al Report CS-1244. New astle University (2011
17. M.Koutny and M.Pietkiewi z-Koutny: Synthesis of Elementary Net Systems with
Context Ar s and Lo alities. Fundamenta Informati ae 88 (2008) 307328
18. U.Montanari and F.Rossi: Contextual Nets. A ta Informati a 32 (1995) 545596
19. G.Rozenberg and J.Engelfriet: Elementary Net Systems. Le ture Notes in Com-
puter S ien e 1491 (1998) 12121
20. A.Yakovlev, M.Kishinevsky, A.Kondratyev and L.Lavagno: et al: OR Causality:
Modelling and Hardware Implementation. Le ture Notes in Computer S ien e 815
(1994) 568587
52