COMPUTING

SCIENCE

Petri Nets and Membrane Computing

J. Kleijn, M. Koutny.

TECHNICAL REPORT SERIES

No. CS-TR-1117 September, 2008

TECHNICAL REPORT SERIES

No. CS-TR-1117 September, 2008

Petri Nets and Membrane Computing

Jetty Kleijn, Maciej Koutny.

Abstract

Petri nets are a well-established model of concurrent and distributed computation

featuring a wealth of tools for the analysis and verification of their behavioural
properties. Like membrane systems, Petri nets are in essence multiset rewriting
systems. Using this key commonality we describe a faithful translation from basic
membrane systems to Petri nets. We also sketch the changes required to deal with
promoters and inhibitors and with dynamically changing membrane structures. To
capture the compartmentisation of membrane systems, the Petri net model is extended
with localities and we show how to adapt the notion of a Petri net process
accordingly. This makes it possible to describe ongoing concurrent behaviour of
membrane systems in terms of causalities between the reactions that are taking place.

© 2008 University of Newcastle upon Tyne.

Printed and published by the University of Newcastle upon Tyne,
Computing Science, Claremont Tower, Claremont Road,
Newcastle upon Tyne, NE1 7RU, England.
Bibliographical details
KLEIJN, J., KOUTNY, M.

Petri Nets and Membrane Computing

[By] J. Kleijn, M. Koutny.

Newcastle upon Tyne: University of Newcastle upon Tyne: Computing Science, 2008.

(University of Newcastle upon Tyne, Computing Science, Technical Report Series, No. CS-TR-1117)

Added entries

UNIVERSITY OF NEWCASTLE UPON TYNE

Computing Science. Technical Report Series. CS-TR-1117

Abstract

Petri nets are a well-established model of concurrent and distributed computation featuring a wealth of tools for
the analysis and verification of their behavioural properties. Like membrane systems, Petri nets are in essence
multiset rewriting systems. Using this key commonality we describe a faithful translation from basic membrane
systems to Petri nets. We also sketch the changes required to deal with promoters and inhibitors and with
dynamically changing membrane structures. To capture the compartmentisation of membrane systems, the Petri
net model is extended with localities and we show how to adapt the notion of a Petri net process accordingly. This
makes it possible to describe ongoing concurrent behaviour of membrane systems in terms of causalities between
the reactions that are taking place.

About the author

Professor Jetty Kleijn is a visiting fellow at the School of Computing Science, Newcastle University.

Maciej Koutny obtained his MSc (1982) and PhD (1984) from the Warsaw University of Technology. In 1985 he
joined the then Computing Laboratory of the University of Newcastle upon Tyne to work as a Research
Associate. In 1986 he became a Lecturer in Computing Science at Newcastle, and in 1994 was promoted to an
established Readership at Newcastle. In 2000 he became a Professor of Computing Science.

Suggested keywords

MEMBRANE SYSTEMS,
P SYSTEMS,
PETRI NETS,
PLACE/TRANSITION NETS,
RANGE ARCS,
LOCALITIES,
GALS SYSTEMS,
CAUSALITY,
PROCESSES,
BARB-EVENTS
Petri Nets and Membrane Computing
Jetty Kleijn1 , Maciej Koutny2
1
Leiden Institute of Advanced Computer Science – LIACS
Leiden University
Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
kleijn@liacs.nl
2
School of Computing Science
Newcastle University
Newcastle upon Tyne, NE1 7RU, United Kingdom
maciej.koutny@ncl.ac.uk

Abstract
Petri nets are a well-established model of concurrent and distributed
computation featuring a wealth of tools for the analysis and verification
of their behavioural properties. Like membrane systems, Petri nets are
in essence multiset rewriting systems. Using this key commonality we
describe a faithful translation from basic membrane systems to Petri
nets. We also sketch the changes required to deal with promoters
and inhibitors and with dynamically changing membrane structures.
To capture the compartmentisation of membrane systems, the Petri
net model is extended with localities and we show how to adapt the
notion of a Petri net process accordingly. This makes it possible to
describe ongoing concurrent behaviour of membrane systems in terms
of causalities between the reactions that are taking place.
Keywords: membrane systems, P systems, Petri nets,
Place/Transition nets, range arcs, localities, GALS systems, causality,
processes, barb-events.

1 Introduction
Membrane systems, or P systems ([45, 46, 47, 57]) are a computational model
inspired by the compartmentisation of living cells and the effect this has
on how they function. The biochemical reactions taking place in the com-
partments of a cell are abstracted to rules specifying which and how many
new objects (molecules) can be produced from objects of a certain kind and
quantity, possibly involving a transfer to a neighbouring compartment. The

1
dynamic aspects of a membrane system and its potential behaviour (its com-
putations) derive from these evolution (or reaction) rules. Thus membrane
computing is essentially concerned with multiset rewriting ([13]).
Petri nets ([20, 48, 52]) on the other hand are an operational model for
concurrent systems directly generalising state machines by their distributed
states and local actions. Thus, a Petri net is essentially a bipartite directed
graph consisting of two kinds of nodes, usually called places and transitions.
Places determine the distribution of the sytem’s states over local states,
whereas transitions are the local actions which when they occur affect only
the information provided by adjacent local states. In Place/Transition nets,
or PT-nets, a typical and prominent Petri net model, system states indicate
the local availability of resources by marking each place with a number of
tokens. When a transition occurs at a state, it consumes some tokens from
each of its input places and produces new tokens in each of its output places.
Hence multiset calculus is also basic for transforming the token distribution
in PT-nets. This key connection between the two models provides the basis
for the faithful translation proposed in [37, 38], from the basic membrane
systems of [46, 47] to PT-nets.
This translation forms the starting point of this chapter as a structural
link between the two models bringing to light the concurrent nature of the
behaviour of membrane systems. Each different kind of objects in a compart-
ment of the membrane system is represented by a different place and each
evolution rule corresponds directly to a transition together with input and
output places. Thus the operational properties of the net reflect the depen-
dencies and independencies (causality, conflict, and concurrency) between
the executions of evolution rules. As a consequence, tools and techniques
developed for Petri nets become available for the description, analysis, and
verification of behavioural properties of membrane systems, and in particular
for the investigation of the structure of ongoing behaviour of membrane sys-
tems. This complements and broadens the standard approach to the analysis
of membrane systems which concentrates primarily on the ultimate results of
‘successful’ or halting computations of membrane systems and on the com-
putational power, including aspects of complexity, of different variants of the
model.
Given the occurrence rule for single transitions, potential concurrency or
synchronicity in the behaviour of a PT-net is captured in a natural way by a
step semantics in terms of arbitrary combinations (multisets or steps) of con-
currently occurring transitions. Both (singleton and arbitrary step) semantics
are standard definitions for the dynamic behaviour of PT-nets. Membrane
systems however are often assumed to evolve in a fully synchronous fashion.
This means that, at each tick of a global clock common to all compartments,
the current configuration of the system is transformed by a maximally concur-
rent (parallel) application of the rules, i.e., no further rules could have been
applied within the same time unit. Thus in this case one would consider

2
for the corresponding PT-nets maximally concurrent steps (as investigated
in [28]).
In addition, their role as a semantic model for membrane systems has
led to a novel extension of Petri nets. In the PT-net constructed from a
membrane system, each transition is given a locality to reflect the compart-
mentisation of the original system. These localities are first of all a modelling
tool — co-located transitions correspond to evolution rules in the same com-
partment — allowing one to identify the active parts of the system during
a computation. But note that the places of PT-nets obtained from mem-
brane systems, support by construction the local aspects of the consumption
and production of resources by the evolution rules represented by the transi-
tions. As a consequence, the localities assigned to transitions are not needed
for a proper interpretation of fully synchronous behaviour of membrane sys-
tems. They play no role in the maximal concurrent step semantics nor in
the singleton or arbitrary step semantics. Localities are however important
in the case of local synchronicity or locally maximal steps, when at each tick
of the global clock and for each locality active during that tick, as many
transitions belonging to this locality as possible are executed. This locally
maximally concurrent semantics is a new and interesting feature for Petri
nets. In fact, PT-nets with localities (or PTL-nets) executing locally max-
imal steps are a model well-suited for the analysis of systems exhibiting a
mix of synchronous and asynchronous executions, i.e., globally asynchronous
locally synchronous (GALS) systems (see [55]). In particular, they provide a
framework for the investigation of membrane systems evolving according to
the natural assumption that synchronicity is restricted to the compartments
of the system as delineated by the membranes.
For the investigation of concurrent runs and in particular of the rela-
tions between transition occurrences during such runs, the notion of process
has been developed for Petri nets. Already in [44], Petri nets are unfolded
into labelled acyclic nets to obtain an explicit represention of causality and
concurency. For various classes of Petri nets, ongoing (potentially infinite)
system behaviour can be investigated using such (infinite) processes (see,
e.g., [6, 7, 22, 30, 31, 44, 53]), a possibility also of interest from a biolog-
ical point of view. Through the translation of basic membrane systems to
PT-nets, processes could provide a convenient, formal, tool for analysing the
causality and (a)synchrony in the behaviour of membrane systems and shed
light on the causal relationships between the reactions taking place during a
computation.
Unfortunately, the strategy for unfolding PT-nets into labelled occurrence
nets does not work for PTL-nets subject to the locally maximal step seman-
tics. The resulting occurrence nets are not true representations of possible
net behaviour, due to a lack of information concerning potential executabil-
ity of transitions which affects the local maximality of executed steps. A
possible solution to this problem is to register explicitly the existence of po-

3
tential alternative occurrences of transitions. This strategy has led in [38] to
the addition of so-called barb-events (or barbs) to processes. Here we will
exemplify this approach and briefly explain why the resulting barb-processes
are sound.
The last part of this chapter is concerned with extensions of basic mem-
brane systems. First we consider membrane systems in which molecules are
not only consumed and produced, but may also act as triggers or inhibitors
of certain reactions [9]. To model this effect we use PTL-nets extended with
range arcs (or PTRL-nets) [33]. Range arcs generalise activator and in-
hibitor arcs, both already existing extensions of the Petri net model (see,
e.g., [12, 48, 27, 56]). These arcs give transitions the possibility to test for
the presence and absence, respectively, of objects (tokens) in specific places
without consuming them. We demonstrate that the translation from basic
membrane systems to PT-nets with localities is robust enough to be gener-
alized to the level of these extended models while retaining the direct corre-
spondence between occurrences of transitions and evolution rules. Thus also
in this more general setting, the synchrony and causal dependence in com-
putations of the membrane system have corresponding interpretations in the
PT-net. Moreover, as shown in [34], again barb-events can be used to extend
the existing process semantics for PT-nets with activator and inhibitor arcs
to a sound process notion for the locally maximal step semantics.
Next, we consider membrane systems with rules which may have an additional
effect on the membranes, dissolving or thickening them. If this happens the
membrane structure changes, the mobility of objects is affected and some
rules may be prevented from ever occurring again. Evolution rules in these
dynamically changing membrane systems cannot be related in a one-to-one
correspondence to Petri net transitions. Still, there is a way of modelling their
characteristics with special control structures using activator and inhibitor
arcs. These control structures correspond uniquely to evolution rules (in a
dynamically changing environment) and consequently, no new Petri net fea-
tures are needed. So, perhaps surprisingly, the behaviour of these membrane
systems can be described and analysed using the barb-processes developed
for PT-nets with localities and activator and inhibitor arcs.
We conclude this chapter with a summary of the presented approach, a
discussion of related work, and possible directions for future research. This
chapter is based on our work reported in [37, 38, 32, 34, 35].

1.1 Notation
A multiset over a (finite, in this chapter) set X is a function m : X → N =
{0, 1, 2, . . .}. Multiset m is said to be empty if there are no x such that
x ∈ m by which we mean that x ∈ X and m(x) ≥ 1. The cardinality of m is
df P
|m| = x∈X m(x).
For two multisets m and m′ over X, the sum m + m′ is the multiset given by

4
 df
(m + m′ )(x) = m(x) + m′ (x) for all x ∈ X, and if k ∈ N then k · m is the
df
multiset given by (k · m)(x) = k · m(x) for all x ∈ X. We denote m ≤ m′
whenever m(x) ≤ m (x) for all x ∈ X, and if m′ ≤ m, then the difference
′
df
m − m′ is (m − m′ )(x) = m(x) − m′ (x) for all x ∈ X.
A multiset over X may be represented (in a non-unique way) as a string of
elements from X; for example, zyzz and yzzz both denote the multiset m
such that m(y) = 1, m(z) = 3 and m(x) = 0 for all x ∈ X \ {y, z}. The empty
string (multiset) will be denoted by λ.
The set of all (closed) intervals of natural numbers is denoted by INT.

2 Basic membrane systems and PTL-nets

2.1 Basic membrane systems
We start from the most basic definition of membrane systems [46].

Definition 2.1 [membrane structure] A membrane structure µ (of degree

m ≥ 1) is given by a rooted tree with m nodes identified with the integers
1, . . . , m. We will write (i, j) ∈ µ or i = parent (j) to mean that there is an
edge from i (parent) to j (child) in the tree of µ, and i ∈ µ to mean that i is
a node of µ.

The nodes of a membrane structure represent nested membranes which in

turn determine compartments. Compartment j is enclosed by membrane j
and lies in-between j and its children (if any). Figure 1 shows a membrane
structure (with m = 5) together with the corresponding compartments. Note
that 1 is the root node, (1, 2) ∈ µ and 3 = parent(5).
In the rest of this section, we will use notions specified in a previous,
numbered definition (like µ above) directly in subsequent definitions.

1
1 3
2
5
2 3
4
4 5

Figure 1: Membrane structure and compartments for the running example.

Each distribution of objects over its compartments determines a configu-

ration of a membrane system.

Definition 2.2 [basic membrane system and its configurations] Let V be a

finite alphabet of names of objects (molecules). A (basic) membrane system

5
 r11 : b → a
1 1 ab
ab r12 : a → b cin2 cin2 ain3
r13 : b → c
2 abcc 3 λ
3
r31 : a → ain4 bin5 cout
2
abcc r32 : b → ain4 bin5
4 b 5 λ

b 4 5 C0 = (ab, abcc, λ, b, λ)
r21 : accc → b
r22 : b → a r41 :
ab →
b bout

Figure 2: A basic membrane system with initial configuration.

df
over µ is a tuple Π = (V, µ, w10 , . . . , wm
0
, R1 , . . . , Rm ) such that, for every
0
membrane i, wi is a multiset of objects, and Ri is a finite set of evolution
rules r of the form lhs r → rhs r , where lhs r 6= λ, is a multiset over V , and
rhs r is a multiset over
V ∪ {aout | a ∈ V } ∪ {ainj | a ∈ V and (i, j) ∈ µ}
such that if i is the root of µ then no aout occurs in rhs r .
df
A configuration of Π is a tuple C = (w1 , . . . , wm ) of multisets of objects, and
df
C0 = (w10 , . . . , wm
0
) is the initial configuration.
We refer to lhs r as the left hand side of the rule r, and rhs r as its right hand
side. The left hand side of a rule specifies which and how many objects are
needed as input for a single execution of this rule and its right hand side
specifies which and how many new objects are produced as a consequence.
A symbol ainj represents an object a that is sent to a child node (compart-
ment) j and aout means that a is sent to the parent node. Figure 2 shows
a basic membrane system over the membrane structure from Figure 1. This
is our running example. In this particular case, V = {a, b, c}, lhs r21 = accc,
rhs r12 = b cin2 cin2 ain3 , w10 = ab and w50 = λ. The initial configuration is
depicted also on the right, by placing the string wi0 next to the node i of the
membrane structure.
A membrane system evolves from configuration to configuration as a con-
sequence of the application (or execution) of evolution rules. Having said
that, there is more than one strategy in which this can be done, ranging from
applying a single rule at a time, to maximal parallelism. We distinguish four
such execution modes, all based on the notion of a vector multi-rule.

6
 1 ab C0 1 ab C1 1 abc C2

2 abcc 3 λ 2 abcccc 3 a 2 abc 3 λ

r
=⇒lmax
r′
=⇒lmax
4 b 5 λ 4 b 5 λ 4 ab 5 b

Figure 3: An lmax-computation for the running example with the vector

multi-rules r = hr11 r12 , λ, λ, λ, λi and r′ = hλ, r21 r22 , r31 , λ, λi.

df
Definition 2.3 [vector multi-rule] A vector multi-rule of Π is a tuple r =
hr1 , . . . , rm i where, for each membrane i of µ, ri is a multiset of rules from
Ri .

We lift the notion of left and right hand sides of rules to vector multi-
rules.
P For a vector multi-rule r as above, we denote by lhs ri the multiset
r
r∈Ri ri (r) · lhs in which all objects in the
Pleft hand sides of the rules in ri
are accumulated, and by rhsri the multiset r∈Ri ri (r) · rhs r of all (indexed)
objects in the right hand sides. The first multiset specifies per compartment
how many objects are needed for the simultaneous execution of a combination
of evolution rules.

Definition 2.4 [enabled vector multi-rule] A vector multi-rule r of Π is

free-enabled at a configuration C if lhs ri ≤ wi , for each i. A free-enabled r
is: min-enabled if |r1 | + · · · + |rm | = 1; max-enabled if no ri can be extended
to yield a vector multi-rule which is free-enabled at C; and lmax-enabled if no
non-empty ri can be extended to yield a vector multi-rule which is free-enabled
at C.

Referring to the running example and considering its initial configuration,

hλ, λ, r31 , λ, λi is not free-enabled, hr11 , λ, λ, λ, λi is min-enabled but not
lmax-enabled, hr11 r12 , λ, λ, λ, λi is lmax-enabled but not max-enabled, and
hr11 r12 , r22 , λ, λ, λi is max-enabled.
If r is free-enabled (free) at a configuration C, then C has in each mem-
brane i enough copies of objects for the application of the multiset of evolu-
tion rules ri . Maximal concurrency (max ) requires that adding any extra rule
makes r demand more objects than C can provide. Locally maximal concur-
rency (lmax ) is similar but in this case only those compartments which have
rules in r cannot enable even more rules; in other words, each compartment
either uses no rule, or uses a maximal multiset of rules. Minimal enabling
(min) allows only a single copy of just one rule to be applied any time.
We now describe the effect of the application of the rules which is inde-
pendent of the mode of execution m ∈ {free, min, max , lmax }.

7
Definition 2.5 [computations] A vector multi-rule r which is m-enabled at
C can m-evolve to a configuration C ′ = (w1′ , . . . wm ′
) such that, for each i and
object a:
X
wi′ (a) = wi (a) − lhs ri (a) + rhs ri (a) + rhs rparent(i) (aini ) + rhs rj (aout )
i=parent(j)

df r
where rhs rparent(i) = λ if i is the root of µ. We denote this by C =⇒m C ′ .
An m-computation is a sequence of m-evolutions starting from C0 .
Note that the evolution of C is non-deterministic in the sense that there may
be different vector multi-rules applicable to C as described above. Figure 3
shows a two-stage lmax-evolution for the running example.

2.2 Place/Transition nets with localities

We now introduce the class of Petri nets to be used for a direct, behaviour
preserving translation from basic membrane systems. To model membrane
systems, multisets of places are used to represent the availability of molecules
within the compartments, while transitions correspond to evolution rules.
As a consequence, each transition is associated with a compartment and
this information is explicitly added to the model through the concept of the
locality of a transition.
Definition 2.6 [PTL-net] A PT-net with localities (or PTL-net) is a tuple
df
NL = (P, T, W, D, M0 ) where P and T are finite disjoint sets of respectively
the places and transitions, D : T → N is a locality mapping, W : (T × P ) ∪
(P × T ) → N is the weight function, and M0 : P → N is the initial marking
(in general, any multiset of places is a marking). We assume that, for every
transition t there is a place p such that W (p, t) 6= 0.
In diagrams, like that in Figure 4, places are drawn as circles, and transitions
as boxes. If W (x, y) ≥ 1 for some (x, y) ∈ (T × P ) ∪ (P × T ), then (x, y) is
an arc leading from x to y. An arc is annotated with its weight if the latter
is greater than one. A marking M is represented by drawing in each place
p exactly M (p) tokens (small black dots). Boxes representing transitions
belonging to the same localities either have the same shade or are displayed
on a grey background of the same shade. The locality mapping D partitions
the transition set by associating with each transition a locality, given by an
integer, for correspondence with compartments.
The role of vector multi-rules is now played by multisets of simultaneously
executed transitions.
Definition 2.7 [step] A step U of NL is a multiset of transitions. Its pre-
multiset P
and post-multiset of places,
P pre(U ) and post(U ), are respectively
given by t∈U U (t) · W (p, t) and t∈U U (t) · W (t, p), for each place p.

8
 As for the basic membrane systems, four modes of execution for PTL-nets
(from sequential to fully synchronous) can be defined and analysed.

Definition 2.8 [enabled step] A step U is free-enabled at a marking M if

pre(U ) ≤ M . A free-enabled U is: min-enabled if |U | = 1; max-enabled if
U cannot be extended to yield a step which is free-enabled at M ; and lmax-
enabled if U cannot be extended by a transition t satisfying D(t) ∈ D(U ) to
yield a step which is free-enabled at M .

Step U is enabled at a marking M if in each place there are enough tokens

for the specified multiple occurrence of each of its transitions (note that each
transition t needs to consume from each place p exactly W (p, t) tokens which
cannot be shared with any other transition). For the PTL-net in Figure 4
and its initial marking, r31 is not free-enabled, r11 is min-enabled but not
lmax-enabled, r11 r12 is lmax-enabled but not max-enabled, and r11 r12 r22 is
max-enabled.

Definition 2.9 [step sequences] A step U which is m-enabled at a marking

df
M can be m-executed leading to the marking M ′ given by M ′ = M −pre(U )+
post(U ). We denote this by M [U im M ′ .
An m-step sequence is a sequence of m-executions starting from M0 .

A possible two-stage lmax-computation for the PTL-net in Figure 4 is:

M0 [r11 r12 ilmax M ′ [r21 r22 r31 ilmax M (†)

where M is as M0 except that M (c:2) = M (c:1) = M (a:4) = M (b:5) = 1.

2.3 From basic membrane systems to PTL-nets

To model a basic membrane system as a PTL-net, we introduce a separate
place (a, j) for each molecule a and membrane j. For each rule r associated
with a compartment i we introduce a separate transition tri with locality i. If
the transformation described by a rule r of compartment i consumes k copies
of molecule a from compartment j, then we introduce a k-weighted arc from
place (a, j) to transition tri , and similarly for molecules being produced. Fi-
nally, assuming that, initially, compartment j contained n copies of molecule
a, we introduce n tokens into place (a, j). This idea is formalised as follows.

Definition 2.10 [translating membrane systems into PTL-nets] The PTL-

df
net corresponding to Π is NLΠ = (P, T, W, D, M0 ), where:
df df
• P = V × {1, . . . , m} and M0 (p) = wj (a) for every place p = (a, j).
df
• T = T1 ∪. . .∪Tm where each Ti consists of distinct transitions t = tri for
df
every evolution rule r ∈ Ri , with locality D(t) = i; and for each place

9
 a:1 r11 b:1
r13 c:1
r12

2 a:3 c:3

c:2 r31
3
r21 a:5
r32
b:5
a:2 b:2 a:4 c:5
r41
b:3
r22 b:4
c:4

Figure 4: PTL-net corresponding to the basic running example.

p = (a, j) the weight of the incoming arc is W (p, t) = lhs r (a) if i = j,

df

df df
and otherwise W (p, t) = 0 and of the outgoing one it is W (t, p) =
rhs r (a) if i = j, W (t, p) = rhs r (aout ) if j = parent (i), W (t, p) =
df df

rhs r (ainj ) if i = parent(j), and otherwise W (t, p) = 0.

df

Figure 4 shows the translation for the running example, where each place
(x, i) is denoted as x:i and each transition tri as r.
To capture the very tight correspondence between the membrane system
Π and the PTL-net NLΠ , we introduce a straightforward bijection between
configurations of Π and markings of NLΠ , based on the correspondence of
object locations and places as well as that of vector multi-rules and steps.
Definition 2.11 [mapping configurations & vector multi-rules] The mark-
ing ν(C) corresponding to configuration C = (w1 , . . . , wm ) is defined by
df
ν(C)(a, i) = wi (a), for every place (a, i).
The step ρ(r) corresponding to vector multi-rule r = (r1 , . . . , rm ) is de-
df
fined by ρ(r)(tri ) = ri (r), for every transition tri .
Fact 2.1 ν(C0 ) = M0 .
For the lmax-computations given in Figure 3 and (†), we have ρ(r′ ) =
r21 r22 r31 and ν(C2 ) = M .

10
 For any translation from membrane systems to Petri nets to be useful,
it is essential to ensure that the latter can provide a faithful representation
of the behaviour of the former. Here, in fact, it is possible to establish the
desired relationship between (the operation of) membrane systems and Petri
nets at the system level. The fundamental link between the dynamics of a
membrane system and that of its corresponding PTL-net is formulated next.
r
Fact 2.2 C =⇒m C ′ if and only if ν(C) [ρ(r)iim ν(C ′ ) in NLΠ , for each
mode of execution m.

Together with Fact 2.1, this immediately implies that the (finite and infinite)
m-computations of Π coincide with m-step sequences of NLΠ . For example,
the lmax-evolution of the running example given in Figure 3 coincides with
that in (†) of the corresponding PTL-net.

2.4 PTL-nets and membrane system analysis

A central reason for defining Petri net models of membrane systems is that
there is a variety of analytical and verification techniques developed over the
years for Petri nets which could be applicable to membrane systems. Some
techniques can be useful to assert properties of reachable configurations; for
example, one can show (via the invariant analysis based on linear algebra [54]
of the PTL-net in Figure 4) that for the basic membrane system in Figure 2
we have 0 ≤ M (a:4) + M (b:3) − M (c:1) ≤ 2, for every marking reachable
from the initial one.
Another way of deploying the analytical power of Petri nets is to use their
causality semantics based on occurrence nets. This kind of analysis and ver-
ification would be oriented more towards dealing with entire computations
rather than concentrating solely on the properties of reachable configurations.
In a nutshell, an occurrence net associated with a PTL-net NL is an abstract
record of a single step sequence of NL in which only information about causal-
ity and concurrency between executed transitions and visited local states is
represented. Together with the natural requirement that causality is acyclic,
this means that the underlying structure of an occurrence net is that of a
partial order.
Consider, for example, the PTL-net NL in Figure 4 and its lmax-
step sequence which executes consecutively the three steps: U1 = r11 r12 ,
U2 = r21 r22 r31 and U3 = r41 . The construction of an occurrence net ON
corresponding to such an lmax-step sequence can be explained as follows.
Referring to Figure 5, we first create 7 places corresponding to the 7 tokens
in the initial marking of NL and labelled accordingly; these places are the only
places marked in the default initial marking of ON (with one token each).
We then take |U1 | = 2 fresh transitions, corresponding (through their labels)
to the transitions in U1 and provide each with the correct inputs from the
places of the initial marking of ON . The execution of U1 creates new tokens;

11
these are again represented as labelled places of ON but, crucially, these new
places are completely fresh. In particular, even though r12 produces tokens
in c:2, we do not draw an arc from r12 to one of the c:2-labelled places in the
initial marking of ON ; rather, we create two brand new c:2-labelled places.
A similar construction is carried out for the remaining two steps U2 and U3 ,
resulting in the net shown in Figure 5 (with one exception explained below).
Essentially, ON traces the changes of markings due to steps being exe-
cuted along some legal behaviour of the original PTL-net, and in doing so
records which resources are consumed and produced. As a result, the origi-
nal net is unfolded into a labelled acyclic net, called a process, representing
the structure of the given step sequence. As is standard in causality analy-
sis of nets, such a representation should allow one to talk about important
behavioural aspects of NLΠ , such as:
• Causality. The causality relationships among the executed transitions
can be read-off by following directed paths in ON .
• Concurrency. Executed transitions without a directed path between
their representations in ON are concurrent.
• Executability. Executions of ON define m-executions of NL.
• Representation. The m-execution of NL on basis of which ON is con-
structed can be executed by ON .

b:4 r41
b:4
a:1
b:3
b:1 r11 r31
a:4
1 a:3 b:5
a:1 r12
c:2 c:1
b:1
c:2
c:2
c:2 r21
b:2
a:2

b:2 r22
a:2

Figure 5: Causal process for the PTL-net in Figure 4.

The third property expresses a soundness condition and implies an obliga-

tion to define an execution semantics for processes consistent with the chosen

12
execution step semantics of the original PTL-net (for a general semantical
framework for Petri net processes, see [30]). In case of m ∈ {free, min, max }
one can use the same step semantics for PTL-nets and their processes, and
the Executability and Representation properties will hold [30]. However, as
was argued in [37, 38], the relatively straightforward unfolding construction
given above may fail to satisfy the Executability property in case of lmax-step
sequences.
To make things work properly in the sense of the theory expounded in [30],
one needs to suitably modify the standard process construction, as first out-
lined in [37]. Firstly, to have an lmax-step sequence semantics for the pro-
cesses, all their transitions will have a locality assigned, corresponding to the
original locality in the PTL-net. Secondly, the processes are augmented with
information about the existence of transitions that could have been chosen
for execution but were not, for example, due to being in conflict with some of
the other executed transitions. In other words, barb-events (barbs) are used
to signal potential executability of transitions in lmax-executions of PTL-
nets. In the example, the transition labelled with 1 and connected to the
b:1-labelled place in the initial marking is such a barb-event. It indicates
that with the initial token in place (b, 1), at this point of the step sequence,
some non-specified transition at location 1 was enabled (but did not occur).
The lmax-enabling rule is now adjusted to use barbs as devices enforcing
lmax-execution within the process net, but they are not meant to be exe-
cuted. In this way, barbs prevent that lmax-step sequences of the process
net postpone the enabling of process transitions when that would imply that
other transitions of the original net (with the same location) should have
been executed.
The complete set of computations of a membrane system combined with
all possible non-deterministic choices at reachable configurations can be rep-
resented by a single object, its reachability graph, an initialised directed
graph with configurations as its nodes and edges labelled with vector multi-
rules leading from cconfiguration to configuration. Moreover, thanks to the
close correspondence between basic membrane systems and their associated
PTL-nets outlined in the previous section, for the purpose of analysis of a
basic membrane system we can also investigate the reachability graph of its
PTL-net as this is isomorphic to the reachability graph of the membrane sys-
tem. Since reachability graphs combine step sequences and reachable states
(markings), they are useful for the analysis and verification of behavioural
properties. Researching properties of reachability graphs has a long tradition
in the field of Petri nets, and has produced over the years several fundamen-
tal insights. One of the crucial results is that the reachability problem
for PT-nets (under the min-step or free-step sequence semantics) is decid-
able [43, 39]. In turn, this immediately implies that the problem of deciding
whether a basic membrane system has a free- or min-computation leading to
a given configuration (desired or non-desired) can be decided, and this result

13
does not depend on the number of reachable configurations which may be
infinite.
Another relevant property which one might want to verify for a basic mem-
brane system is whether the concentration of specific molecule(s) in specific
compartment(s) can grow unboundedly during one of its possible computa-
tions. This problem, referred to as boundedness, can also be tackled within
the Petri net domain where it is shown to be decidable using the coverability
tree construction introduced in [29] and then investigated, among others,
in [24, 48]. What is more, coverability trees can also provide a tool for de-
ciding many other relevant behaviourial problems, such as mutual exclusion,
i.e., to show that two kind of molecules cannot be simultaneously present in
the same compartment.

3 Extensions
Motivated by natural phenomena in biological systems, a whole range of dif-
ferent extensions of the basic membrane system have been introduced often
in the form of more sophisticated evolution rules. For some of these ex-
tensions, like catalysts and symport/antiport rules, the basic translation to
PTL-nets can be used as before. For others, like i/o communication and
rule creation/consumption, the correspondence between evolution rules and
Petri net transitions is slightly more involved, but the resulting nets are again
PTL-nets (see [32]). However, not all interesting variants of membrane sys-
tems can be modeled using no more than the PTL-net model. In this section,
we discuss two such models and sketch how they can be properly captured
in a suitably extended PTL-net model.

3.1 Rules with promoters and inhibitors

First we consider an extended version of membrane systems for modeling how
reactions may be triggered or blocked in the presence of certain molecules.
The role of such molecules differs from that of catalysts which actively take
part in reactions and are returned afterwards. An example is object b
which acts as a catalyst in evolution rule r41 : ab → b bout of our running
example (see Figure 2). To model the subtle effect that the presence of
molecules may have, membrane systems have evolution rules r of the form
lhs r → rhs r |pro r , inh r where pro r and inh r are multisets over V specifying re-
spectively the promoters and inhibitors of r. The intuition behind pro r and
inh r is that they test respectively for the presence and absence of certain
objects inside a compartment, but without consuming them. As a conse-
quence, any number of rules can test for the presence of a single object at the
same time. In order for r to occur there must be at least pro r (a) copies of
each symbol a in its associated compartment, and less than inh r (a) copies of

14
each symbol a which occurs in inh r . (Thus if inh r = λ, the empty multiset,
no object inhibits by its presence the occurrence of rule r.) It is assumed
without loss of generality, that pro r (a) < inh r (a) for all rules r and symbols
a ∈ inh r . We retain all definitions introduced for basic membrane systems in
Subsection 2.1 with only one change regarding the notion of a free-enabled
vector multi-rule r. This is strengthened by additionally requiring that, for
each i and r ∈ ri , we have pro ri ≤ wi and, moreover, if a ∈ inh r then
wi (a) < inh r (a).
PTL-nets are not expressive enough to model inhibitors and promoters
because arcs between transitions and places indicate consumption and pro-
duction of tokens (objects) rather than testing for their presence or absence.
A possible way out is to use PTL-nets extended with range arcs [33]. Each
such arc links a place to a transition and is specified by an interval (possibly
infinite) of non-negative integers. This interval indicates the range (in the set
INT) for the number of tokens that should be present in the place to enable
the occurrence of the transition. Clearly, like pro r and inh r , range arcs can
be used to model certain forbidden/required concentrations of molecules in
a compartment.
A PT-net with range arcs and localities (or PTRL-net) is a tuple
df
N RL = (P, T, W, R, D, M0 ) where the components other than R are as in Def-
inition 2.6, and R : P × T → INT defines the range arcs. Let R(p, t) = [k, l]
be the interval associated as a range arc from place p to transition t. In
diagrams, R(p, t) is drawn as an arrow from p to t with a small grey circle as
arrowhead and annotated with (k, l). There are two important special cases:
• k = 0 = l. Then the range arc is an inhibitor arc, p is an inhibitor
place of t, and t can only be executed if p does not contain any tokens
(we draw an arrow from p to t with a small open circle as arrowhead).
• k = 1 and l = ∞. Then the range arc is an activator arc, p is an
activator place of t, and t can only be executed if p contains at least
one token (we draw an arrow from p to t with a small black circle as
arrowhead).
As far as the behaviour is concerned, all we need to do is to stipulate that a
step U is free-enabled at a marking M if, in addition to the requirements in
Definition 2.8, for every place p ∈ P and transition t ∈ U , we have M (p) ∈
R(p, t).
The translation from membrane systems to PTRL-nets proceeds as in
Definition 2.10 for the case of basic membrane system. The only additional
feature is that for each transition t = tri and place p = (a, j), we introduce a
df df
range arc such that R(p, t) = [0, ∞] whenever i 6= j, and otherwise R(p, t) =
[pro r (a), inh r (a) − 1] if a ∈ inh r and R(p, t) = [pro r (a), ∞] if a ∈
/ inh r .
df

Figure 6 illustrates the modified translation. It may be of interest to compare

in Figures 4 and 6 the different translations of the role of b in rule r41 .

15
 In [34], it has been shown that key properties of the modified translation
are very similar to those obtained in the basic case; in particular, Defini-
tion 2.11 and Fact 2.2 can simply be restated. Moreover, the treatment of
causality developed for PTL-nets can be extended to PTRL-nets after allow-
ing activator arcs in the occurrence nets (see [33, 34]).
When it comes to the properties which might be expressed or investigated
using reachability or coverability graphs, the situation changes dramatically
when we move from PTL-nets to PTRL-nets. The reason is that PTRL-nets
allow one to test for the absence of resources (zero-testing). Nets with this
kind of relationship between places and transitions (i.e., inhibitor arcs) have
been considered in [1, 26, 48]. The extension with inhibitor arcs gives the
resulting model of Petri nets the expressive power of Turing machines and
decidability for certain important behavioural properties, such as reachability
and boundedness, is lost [25, 1]. Although boundedness (like reachability)
is undecidable for general PT-nets with inhibitor arcs, partial solutions have
been proposed by restricting the class of nets under consideration as, for
example, in [10].

a:1 r11 b:1

r13 c:1
r12
a:3 c:3
2

c:2 r31
(2,3)
3
r21 a:5
r32
b:5
a:2 b:2 a:4 c:5
r41
b:3
r22 b:4
c:4

Figure 6: PTRL-net model of the running example with added promoter and
inhibitor constraints. The membrane system is as in Figure 2 except that
r13 : b → c|λ , c , r21 : accc → b|cc, cccc and r41 : a → bout |b , λ .

16
 a:1 r11 b:1
r13 c:1
r12

2 a:3 c:3

c:2 τ :2 r31 r31

3
r21 a:5
r32
b:5
δ:4
a:2 b:2 a:4 c:5
r41
b:3
r22 b:4
r32
c:4

Figure 7: PTRL-net model of the running example with added membrane

thickening and dissolving features. The membrane system is as in Figure 2
except that r21 : accc → b|τ and r41 : ab → bbout |δ . There are now two copies
of the transitions for r31 and r32 . Note that only the essential additional
places are shown.

3.2 Thickening and dissolving membranes

What may come as a surprise, is that PTRL-nets are also robust enough to
model in a faithful way, membrane systems with a dynamic structure due to
rules which may thicken or dissolve membranes. Evolution rules are now
of the form lhs r → rhs r |τ or lhs r → rhs r |δ .
The first rule is annotated with the special symbol τ which indicates
that, when executed, r causes its immediately enclosing membrane to be-
come ‘thick’, and no object can pass through it anymore [46]. The transla-
tion to PTRL-nets can proceed as before (Definition 2.10), but to capture
the thickening of membranes in addition, for each membrane i a single spe-
cial initially empty control place τ :i is introduced as an extra output place
for all transitions which correspond to rules which make membrane i thick
(thus there may be several transitions inserting tokens into τ :i). Then each
transition corresponding to a rule transferring objects through membrane i,
is connected to τ :i by an inhibitor arc. As a result, as long as no transition
which produces a token in τ :i is executed, the execution of transitions trans-

17
ferring objects through membrane i is not affected. However, once there is
at least one token in τ :i, these transitions can no longer be executed because
no transition ever removes a token from τ :i. Figure 7 illustrates the modified
translation for the running example in which r21 is now a thickening rule.
As in the case of membrane systems with inhibitors and promoters, the key
properties of the resulting PTRL-nets are similar to those obtained in the
basic case.
It is however more complicated to deal with rules which may lead to the
dissolution of membranes. The special symbol δ in lhs r → rhs r |δ indicates
that this rule, when executed in some compartment i enclosed by a membrane
different from the root membrane, causes the membrane to ‘dissolve’ [45, 46].
Moreover, all objects present in that compartment are incorporated into com-
partment parent (i), and all rules formerly associated to compartment i are
prevented from ever occurring in the future. The basic translation to PTL-
nets is now modified in the following way. To model evolution rules from
compartment parent(i) as transitions having access to the tokens stored in
the places representing objects in the former compartment i, we use copies of
transitions and activator and inhibitor arcs to signal which membranes have
been dissolved. For each membrane i that can be dissolved, a membrane sta-
tus control place δ:i is introduced. Each transition representing a dissolving
rule associated with compartment i has δ:i as an additional output place. All
transitions associated with membrane i are connected with an inhibitor arc to
place δ:i. Hence once the membrane has been dissolved, they can never occur
again. Rules associated with a membrane with a nested sequence of dissolv-
ing descendant membranes will be represented by transitions for each possible
combination of access to resources. This can be modelled by a combination
of activator and inhibitor arcs (see [35]). Consider, for example, a membrane
system with three membranes such that 1 = parent (2) and 2 = parent (3).
Assume further that there are two dissolution rules, r′ within membrane 2
and r′′ within 3. Then we add two membrane status places, δ:2 and δ:3,
each place being initially empty and having an incoming directed arc from
′ ′′
transition tr2 and tr3 , respectively. Then, given a rule r : a → aa associated
with membrane 2, we construct two transitions with locality 2 and a directed
arc of weight 2 to place a:2, viz. tr,2 with a directed arc from a:2, and tr,3
with a directed arc from a:3. We also add an inhibitor arc between δ:2 and
each of these two transitions, as well as an activator arc between tr,3 and δ:3.
As a result, tr,2 can be executed only if r′ has not occurred whereas tr,3 only
if r′ has not occurred but r′′ has occurred.
Figure 7 illustrates the construction for the running example in which r41 is
now a dissolving rule.
It has been shown in [35] that key properties of the modified translation
are similar to those obtained in the basic case; however, Definition 2.11 and
Fact 2.2 cannot simply be restated. The reason is that more than one tran-
sition can correspond to a single rule, as in the case of tr,2 and tr,3 above.

18
As a consequence, when comparing the computations of a membrane system
with dissolving rules with the step sequences of a corresponding PTRL-net,
we need to treat executions of transitions like tr,2 and tr,3 as if they were
the same transition. This is a standard approach in Petri net theory when
one deals with nets with labelled transitions with equal labelling identifying
semantically equivalent transitions. As demonstrated in [35], having more
transitions in the PTRL-net than rules in the original membrane system
cannot be avoided if the step sequences should correspond to computations.
Finally, the constructions outlined above can be adapted to simulate also si-
multaneous executions of thickening and dissolving of membranes as allowed
in [46].

4 Concluding remarks
The faithful translation of basic membrane systems into PT-nets (with lo-
calities) has been the starting point of this chapter. The main contribution
of the work presented is its potential for further development and exploita-
tion of this structural and systematic link between membrane systems and
Petri nets. For membrane systems this means that results, techniques, and
tools from the Petri net world become available, like linear algebra techniques
(invariants), and coverability and reachability analysis including decidability
results and verification techniques (model checking). Moreover, with the pro-
cess semantics of Petri nets, it becomes possible to describe the concurrent
behaviour of membrane systems in terms of causal dependencies between
executions of evolution rules. For Petri nets the direct connection with mem-
brane systems has led to new, interesting notions like locality (PTL-nets) and
locally maximal step sequence semantics, necessitating research into a new
process semantics suitable for PT-nets modelling GALS systems. Moreover,
it has been pointed out how also membrane systems with more involved fea-
tures like promoters and inhibitors could be related to PTL-nets with range
arcs (to test the concentration of molecules inside compartments). The obser-
vation that even dynamic structure, resulting from membrane thickening and
dissolving, can be hard-coded within the PTRL-net model seems to indicate
that Petri nets in general, and PTRL-nets in particular, provide a robust and
uniform framework which can be employed as a convenient and powerful tool
for analysing the computations of membrane systems.

4.1 Related work

The interpretation of the evolution (reaction) rules of a membrane system
as Petri net transitions is a quite natural idea and appears in various places
in the literature, e.g., in [17, 50] which both also regard the connection of
(variants of) membrane systems to Petri nets as an opportunity to describe

19
behavioural aspects of membrane systems and make results from the realm of
Petri nets available for the analysis of membrane computations. In [21] on the
other hand, Petri nets are used to describe features capturing the computa-
tional completeness of P systems. In [4] the relationship between membrane
systems and Petri nets is investigated on basis of two different membrane
system interpretations of the producer/consumer example. A completely
different approach is followed by [2] for P systems with symport/antiport
rules. The hierarchy of a membrane structure is reflected in an hierarchy
of agents, each modelled by a Petri net with nets as tokens. Molecules are
represented by unstructured (ordinary) tokens and exchanging molecules is
modelled by agents exchanging subagents. Actually, also the containment
relation of higher-level agents can change dynamically when transitions are
executed, which makes it possible to investigate in the future also P systems
with active membranes. It is shown in [19] how PB systems (membrane sys-
tems with boundary rules) and membrane dissolution and creation can be
‘weakly’ simulated by Petri nets as a means to investigate the decidability
status of reachability and boundedness for such membrane systems. This
extends the work for PB systems with static membrane structure from [17].
In an attempt to relate P systems to the Petri net model for simulation and
decidability purposes, [23, 49] propose an approach based on a new Petri net
model with dynamic rewriting of descriptive expressions.
Other related work is concerned with the synthesis of Petri nets with lo-
calities and inhibitor arcs and activator arcs from behavioural descriptions
in the form of step transition systems (i.e., state graphs with step-labelled
edges). More precisely, given a step transition system one is asked to con-
struct a net with an isomorphic reachability graph. This problem has been
first investigated for the class of elementary net systems in [40, 41] and the
solution was extended to other classes of nets, including PTRL-nets, in [18].
Next to Petri nets, also other models for concurrent and mobile systems
have been applied as a framework for the investigation of the behaviour of
membrane systems. In particular, calculi with membranes have been consid-
ered including ways to describe through such bioinspired calculi the causal de-
pendencies among the reactions taking place in membrane systems (see, e.g.,
[11, 8, 15, 14, 16, 51] and also Chapter 20 of this volume). In [5] the mod-
elling methods of membrane systems, π-calculus, Petri nets, and two tools
are combined and compared.

4.2 Further outlook

The translation given in Definition 2.10 provides a fundamental connection
between membrane systems and Petri nets. It essentially relates evolution
rules to Petri net transitions at a most basic level with the local aspects of
consumption and production of resources taken care of by the correspondence
between places and located objects. This is immediately clear from Fact. 2.2

20
for the execution mode min (single rules correspond to single transitions) and
then also for the free and max modes. So, localities of transitions play no role
in these semantics. Actually, since the localities of the transitions as defined
by the translation can be deduced immediately from the location of their
input places, even the lmax mode could have been defined without explicitly
specifying localities. It can be argued that what appears to be most robust in
the modelling approach described here is the idea of representing molecules
in different compartments using dedicated places. In particular, there is no
reason why the localities of a PTL-net should be ordered in a hierarchical
(tree-like) structure. Consequently, as already pointed out in [32], the current
scheme can also be used to model, e.g., tissue systems [42] as Petri nets. It
would be interesting to investigate what aspects of this Petri net modelling
approach would still be relevant if other, increasingly sophisticated, classes
of membrane systems were to be considered.
Having transitions associated with specific spatially disjoint locations is
however important from a modelling point of view as they allow to specify
what happens where. The lmax-step sequences of PTL-nets provide a frame-
work for the investigation of membrane systems evolving according to the
natural assumption that synchronicity is restricted to the compartments of
the system as delineated by the membranes. Note that the localities of transi-
tions in PTL-nets do not necessarily depend on the specific input and output
places per transition. Still, one could see localities as providing information
on relationships between membranes or compartments within a single cell.
If one abandons the idea that the ‘localities’ of different cells are disjoint,
then one needs to look for Petri net models more expressive than PTL-nets
or PTRL-nets. For example, in the networks of cells introduced in [3, 4]
evolution rules are not by definition tied to individual compartments or bor-
ders between two membranes. As a result, PTRL-nets may then not be able
to properly reflect the lmax-execution rule defined for networks of cells. It
appears that this is due to the fact that the locality mapping implicitly splits
the space where the evolution rules operate onto disjoint fragments, and so
a possible solution could be a more sophisticated locality mapping. Such a
solution would require a re-definition of lmax-enabledness, perhaps using the
general framework of firing policies introduced in [18] which subsumes under
a single definition a variety of execution modes, including all those considered
in this paper.
Localities are also important for the formalisation of dynamically chang-
ing membrane structures. They provide a means to model which evolution
rules should be ‘switched on’ or ‘switched off’ depending on the presence of
an enclosing membrane. The construction discussed here to model the effect
of thickening and dissolving the membranes fits neatly in the PTRL-net set-
up and should still be useful for more complex classes of membrane systems.
For example, a simple modification using general k weighted inhibitor and
activator arcs should be enough to capture the behaviour of membranes with

21
variable permeability.
Another direction for research aimed at providing support for dealing with
behavioural properties of membrane systems using their established connec-
tion with Petri nets is to investigate specialised analysis techniques that can
be used in dealing with PTRL-nets. As remarked before, properties like
reachability and boundedness are undecidable for these nets. In [36] it is
investigated to what extent the classical coverability tree construction might
be adapted for Petri nets with inhibitor arcs and a step sequence semantics.
PT-nets with localities and range arcs provide a uniform common frame-
work for the systematic investigation of many different variants of membrane
systems. To understand concurrency and dependence relations in the be-
haviours of these nets (and hence of membrane systems) one should develop
a causal semantics appropriate for the chosen operational semantics. The
process semantics outlined here is no more than a first step on the way to
understand the role and effect of localities in the behaviour of such systems.
It is not yet known what are the typical properties of such processes and,
closely related to this, what are the abstract concurrency structures under-
lying such processes (causal partial orders or even the extended causality
structures of [27, 30] are insufficient to capture the intricacies of the inter-
play between local synchrony and causality). A related objective would be
to investigate the notions of conflict and choice in relation to the barb-events
leading to a suitable notion of unfolding for PTRL-nets that could be the
basis for efficient verification procedures.
Finally, the relation between Petri nets and membrane computing as for-
malized here through the concept of PTRL-nets should be compared and
combined with fundamental insights and ideas gained in other investigations
in the general area of natural computing.

References
[1] T.Agerwala, A Complete Model for Representing the Coordination of
Asynchronous Processes, Hopkins Computer Research Report 32, Johns
Hopkins University, 1974
[2] L.Bernardinello, N.Bonzanni, M.Mascheroni and L.Pomello, Modeling
symport/antiport P systems with a class of hierarchical Petri nets, Lec-
ture Notes in Computer Science, 4860, 2007, 124-137
[3] F.Bernardini, M.Gheorghe, M.Margenstern and S.Verlan, Networks of
cells and Petri nets, 5th BWMC, Sevilla, 2007, 33-62
[4] F.Bernardini, M.Gheorghe, M.Margenstern and S.Verlan, Pro-
ducer/consumer in membrane systems and Petri nets, Lecture Notes in
Computer Science, 4497, 2007, 43-52

22
 [5] F.Bernardini, M.Gheorghe, F.J.Romero-Campero and N.Walkinshaw, A
hybrid approach to modeling biological systems, Lecture Notes in Com-
puter Science, 4860, 2007, 138-159
[6] E.Best and R.Devillers, Sequential and concurrent behaviour in Petri
net theory, Theoretical Computer Science, 55, 1988, 87-136
[7] E.Best and C.Fernández, Nonsequential Processes. A Petri Net View,
EATCS Monographs on Theoretical Computer Science, Springer, 1988
[8] A.Bogdana and G.Ciobanu, Translating mobile ambients into P systems,
ENTCS, 171, 2007, 11-23
[9] P.Bottoni, C.Martı́n-Vide, Gh.Păun and G.Rozenberg, Membrane sys-
tems with promoters/inhibitors, Acta Informatica, 38, 2002, 695-720
[10] N.Busi, Analysis issues in Petri nets with inhibitor arcs, Theoretical
Computer Science, 275, 2002, 127-177
[11] N.Busi, Causality in membrane systems, Lecture Notes in Computer
Science, 4860, 2007, 160-171
[12] N.Busi and G.M.Pinna, Process semantics for place/transition nets with
inhibitor and read arcs, Fundamenta Informaticae, 40, 1999, 165-197
[13] C.S.Calude, Gh.Păun, G.Rozenberg and A.Salomaa (Eds.), Multiset
Processing. Mathematical, Computer Science, and Molecular Comput-
ing Points of View, Lecture Notes in Computer Science, 2235, Springer,
2001
[14] L.Cardelli, Brane calculi, Lecture Notes in Computer Science, 3082,
2005, 257-278
[15] L.Cardelli and A.Gordon, Mobile ambients, Lecture Notes in Computer
Science, 1378, 1998, 140-155
[16] G.Ciobanu and D.Lucanu, Events, causality and concurrency in mem-
brane systems, Lecture Notes in Computer Science, 4860, 2007, 209-227
[17] S.Dal Zilio and E.Formenti, On the dynamics of PB systems: a Petri
net view, Lecture Notes in Computer Science, 2933, 2004, 153-167
[18] Ph.Darondeau, M.Koutny, M.Pietkiewicz-Koutny and A.Yakovlev, Syn-
thesis of nets with step firing policies, Lecture Notes in Computer Sci-
ence, 5062, 2008, 112-131
[19] G.Delzanno and L.Van Begin, On the dynamics of PB systems with
volatile membranes, Lecture Notes in Computer Science, 4860, 2007,
240-256
[20] J.Desel, W.Reisig and G.Rozenberg (Eds.), Lectures on Concurrency and
Petri Nets, Lecture Notes in Computer Science 3098, Springer, 2004
[21] P.Frisco, P systems, Petri nets, and program machines, Lecture Notes in
Computer Science, 3850, 2005, 209-223
[22] U.Goltz and W.Reisig, The non-sequential behaviour of Petri nets, In-
formation and Control, 57, 1983, 125-147

23
[23] E.Guţuleac, Descriptive timed membrane Petri nets for modelling of
parallel computing, Int. J. Computers, Communications and Control,
I(3), 2006, 33-39
[24] M.Hack, Decision Problems for Petri Nets and Vector Addition Systems,
Technical Memo 59, Project MAC, MIT (1975)
[25] M.Hack, Petri Net Languages, Technical Report 159, MIT (1976)
[26] M.Hack: Decidability Questions for Petri Nets, PhD Thesis, MIT (1976)
[27] R.Janicki and M.Koutny, Semantics of inhibitor nets, Information and
Computation, 123, 1995, 1-16
[28] R.Janicki, P.E.Lauer, M.Koutny and R.Devillers, Concurrent and max-
imally concurrent evolution of nonsequential systems, Theoretical Com-
puter Science, 43, 1986, 213-238
[29] R.M.Karp and R.E.Miller, Parallel program schemata, J. Comput. Syst.
Sci., 3, 1969, 147-195
[30] H.C.M.Kleijn and M.Koutny, Process semantics of general inhibitor nets,
Information and Computation, 190, 2004, 18-69
[31] H.C.M.Kleijn and M.Koutny, Infinite process semantics of inhibitor nets,
Lecture Notes in Computer Science, 4024, 2006, 282-301
[32] J.Kleijn and M.Koutny, Synchrony and asynchrony in membrane sys-
tems, Lecture Notes in Computer Science, 4361, 2006, 66-85
[33] J.Kleijn and M.Koutny, Processes of Petri nets with range testing, Fun-
damenta Informaticae, 80, 2007, 199-219
[34] J.Kleijn and M.Koutny, Processes of membrane systems with promoters
and inhibitors, Theoretical Computer Science, 404, 2008, 112-126
[35] J.Kleijn and M.Koutny, A Petri net model for membrane systems with
dynamic structure, Natural Computing, to appear
[36] J.Kleijn and M.Koutny, Steps and coverability in inhibitor nets, submit-
ted
[37] J.Kleijn, M.Koutny and G.Rozenberg, Towards a Petri net semantics
for membrane systems, Lecture Notes in Computer Science, 3850, 2006,
292-309
[38] J.Kleijn, M.Koutny and G.Rozenberg, Process semantics for membrane
systems, Journal of Automata, Languages and Combinatorics, 11, 2006,
321-340
[39] S.R.Kosaraju, Decidability of reachability in vector addition systems,
STOC, 82, 1982, 267-281
[40] M.Koutny and M.Pietkiewicz-Koutny, Transition systems of elementary
net systems with localities, Lecture Notes in Computer Science, 4137,
2006, 173-187
[41] M.Koutny and M.Pietkiewicz-Koutny, Synthesis of elementary net sys-
tems with context arcs and localities, Lecture Notes in Computer Sci-
ence, 4546, 2007, 1-300

24
[42] C.Martı́n-Vide, Gh.Păun, J.Pazos and A.Rodrı́guez-Patón, Tissue P sys-
tems, Theoretical Computer Science, 296, 2003, 295-326
[43] E.W.Mayr, An algorithm for the general Petri net reachability problem,
SIAM J. Comput., 13, 1984, 441-460
[44] M.Nielsen, G.Plotkin and G.Winskel, Petri nets, event structures and
domains, Part I, Theoretical Computer Science, 13, 1980, 85-108
[45] Gh.Păun, Computing with membranes, Journal of Computer and Sys-
tem Sciences, 61, 2000, 108-143
[46] Gh.Păun, Membrane Computing. An Introduction, Springer-Verlag,
2002
[47] Gh.Păun and G.Rozenberg, A Guide to membrane computing, Theoret-
ical Computer Science, 287, 2002, 73-100
[48] J.L.Peterson, Petri Net Theory and the Modeling of Systems, Prentice
Hall, 1981
[49] A.Profir, E.Guţuleac and E. Boian, Encoding continuous-time P systems
with descriptive times Petri nets, TAPS’05, IEEE Computer Press ,
2005, 91-94
[50] Z.Qi, J.You and H.Mao, P systems and Petri nets, Lecture Notes in
Computer Science, 2933, 2004, 286-303
[51] A.Regev, E.M.Panina, W.Silverman, L.Cardelli and E.Y.Shapiro,
BioAmbients: an abstraction for biological compartments, Theoretical
Computer Science, 325, 2004, 141-167
[52] W.Reisig and G.Rozenberg (Eds.), Lectures on Petri Nets, Lecture Notes
in Computer Science 1491 and 1492, Springer, 1998
[53] G.Rozenberg and J.Engelfriet, Elementary net systems, Lecture Notes
in Computer Science, 1491, 1998, 12-121
[54] M.Silva, E.Teruel and J.M.Colom, Linear algebraic and linear program-
ming techniques for the analysis of place/transition net systems, Lecture
Notes in Computer Science, 1491, 1998, 309-373
[55] C.Stahl, W.Reisig and M.Krstić, Hazard detection in a GALS wrapper:
a case study, ACSD’05, IEEE Computer Society, 2005, 234-243
[56] W.Vogler, Partial Order Semantics and Read Arcs, Theoretical Com-
puter Science, 286, 2002, 33–63
[57] Membrane systems web page: http://psystems.disco.unimib.it/

25