Networks of Cells and Petri Nets

Networks of Cells and Petri Nets Francesco Bernardini1, Marian Gheorghe2, Maurice Margenstern3, Sergey Verlan4 1Leiden Institute of Advanced Computer Science, Universiteit Leiden Niels Bohrweg 1, 2333 CA Leiden, The Netherlands [email protected] 2Department of Computer Science, The University of Sheffield Regent Court, Portobello Street, Sheffield S1 4DP, UK [email protected] 3Universit´e Paul Verlaine - Metz, UFR MIM, LITA, EA 3097 Ile du Saulcy, 57045 Metz C´edex, France [email protected] 4LACL, D´epartement Informatique, Universit´e Paris 12 61 av. G´en´eral de Gaulle, 94010 Cr´eteil, France [email protected] Summary. We introduce a new class of P systems, called networks of cells, with rules allowing several cells to simultaneously interact with each other in order to produce some new objects inside some other output cells. We define different types of behavior for networks of cells by considering alternative strategies for the application of the rules: sequential application, free parallelism, maximal parallelism, locally-maximal parallelism and minimal parallelism. We devise a way for translating network of cells into placetransition nets with localities (PTL-nets, for short) - a specific class of Petri nets. Then, for such a construction, we show a behavioral equivalence between network of cells and corresponding PTL-nets only in the case maximal parallelism, sequential execution, and free parallelism, whereas we observe that, in the case of locally-maximal parallelism and minimal parallelism, the corresponding PTL-nets are not always able to mimic the behavior of network of cells. Also, we address the reverse problem of finding a corresponding network of cells for a given PTL-net by obtaining similar results concerning the relationships between their semantics. Finally, we present network-of-cells-based models of two classical synchronization problems: producer/consumer and dining philosophers. 1 Introduction Membrane computing is an emerging branch of natural computing which deals with distributed and parallel computing devices of a bio-inspired type, which are called membrane systems or P systems (see [17], [18], and also [1] for a comprehensive bibliography). P systems, originally devised by Gh. P˘aun in [17], are introduced as computing devices which abstract from the structure and functioning 34 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan of living cells - they are defined as a hierarchical arrangement of regions delimited by membranes (membrane structure), with each region having associated a multiset of objects and a finite set of rules. Rules typically encode mechanisms for consuming/producing objects (evolution) and mechanisms for moving objects across the membranes (communication). For consuming/producing objects, multiset rewriting (i.e., replacing a multiset with another one) is the most generally used mechanism, whereas, for communication, various mechanisms with different biological inspiration have been proposed such as: targets here, in, out [18], symport/antiport [18], conditional uniport [25], boundary rules [4], and carriers [16]. In particular, symport/antiport, conditional uniport and boundary rules introduce in P systems the concept of coupled transport: communication is achieved through cooperation between two or more objects possibly placed in two distinct regions - the inside and the outside of a membrane. The class of P systems was later extended to tissue P systems [15, 19] – a variant of P systems where the underlying structure is defined as an arbitrary graph. Nodes in the graph represent cells which are able to communicate objects alongside the edges of this graph. Specifically, for this communication, the mechanisms of symport/antiport and conditional uniport are transferred to tissue P systems [18, 25] so to have models where communication is achieved through interactions between two neighboring cells (i.e., two cells which are directly connected by means of an edge in the underlying graph). Moreover, it is possible to have tissue P systems where a cell receives objects from a neighboring cell non-deterministically chosen [3], or where a cell produces signals which are replicated and simultaneously sent to all neighboring cells [15]. The work done in [7, 13, 12] then showed that the aforementioned features of transformation and communication in P systems can be interpreted as transitions in place-transition nets (PT-nets, for short) – a specific class of Petri nets (e.g., see [21, 22, 8, 11]). This is done by mapping each rule into a transition with places corresponding to the left-hand side of the rule as input, and with places corresponding to the right-hand side of the rule as output; each place in fact represent the occurrence of a certain object inside a certain membrane. Thus, production/consumption of objects and movement of objects across the membranes are both reflected into modifications on the distributions of tokens inside the places of a PT-net. Specifically, this construction was initially applied in [7] to P systems with boundary rules - which encompass symport/antiport and conditional uniport too - and then re-used in [13, 12] for the basic model of P systems where communication is controlled by targets here, in, out. Moreover, contributions [13, 12] devise a formal framework for describing the behavior of P systems in terms of causality/concurrency and for reasoning about reachability, conflicts and soundness of these systems by starting from their translation into PT-nets; this is done by using the PT-net representation of a membrane system is therefore to define the semantics of these systems in terms of sequences of events which consume some resources in order to produce some new ones (process semantics). This construction, which is a standard asynchronous PT-net, is extended in [12, 13] to PT-nets operating in a maximally parallel way and to PT-nets with localities operating in a locally- Networks of Cells and Petri Nets 35 maximal parallel way. PT-nets with localities are a class of PT-nets introduced in [13] where each transition belongs to certain location, in a way that resembles the distribution of the rules over the various regions of a membrane system. This makes possible to distinguish between the globally and locally synchronous behavior (maximal parallelism), globally asynchronous but locally synchronous behavior (locally-maximal parallelism), and asynchronous behavior. In this paper, we introduce a new class of P systems which we call networks of cells. Network of cells are characterized by rules which allow several cells to simultaneously interact with each other in order to produce some new objects inside some other output cells. They are motivated by the observation made in [24] that basic forms of coupled transport like symport/antiport can be expressed in terms of two cells synchronizing on certain inputs in order to produce some outputs. In this respect, networks of cells are not limited to have only two synchronizing cells on their left-hand side and two output cells on their right-hand side. Then, similarly to what was done [13, 12], we define different types of behavior for networks of cells by considering different strategies for the application of the rules: sequential application, free parallelism, maximal parallelism and locally-maximal parallelism plus minimal parallelism [6]. Next, we extend to networks of cells the construction devised in [7, 13, 12] for translating membrane systems into PT-nets with localities (PTL-net, for short) by showing that interaction rules of networks of cells can still be represented as transitions of PTL-nets. However, we are able to establish a behavioral equivalence between network of cells and corresponding PTL-nets only in the case maximal parallelism, sequential execution, and free parallelism (i.e., only for globally and locally synchronous behavior, and asynchronous behavior) as we observe that, in the case of locally-maximal parallelism and minimal parallelism, the corresponding PTL-net is not always able to mimic the behavior of the original network of cells. This allows us to point out differences between the concept of cells used in our model and that of locality introduced in [13] for PT-nets. Also, we address the reverse problem of finding a corresponding network of cells for a given PTL-net by obtaining similar results concerning the relationships between their semantics. Finally we present network-of-cells-based models of two classical synchronization problems: producer/consumer and dining philosophers. These are devised by starting from existing PT-net solutions with the aim of illustrating differences in the two modeling approaches. 2 Preliminaries We recall some basic notions concerning strings and multisets (e.g., see [23, 18] for further details). An alphabet is any finite and non-empty set. The elements of an alphabet are called symbols. Let Vbe an alphabet. A string over Vis any finite sequence consisting of zero or more symbols from V; the same symbol may occur repeated several times inside the same string. The sequence containing no symbols is called 36 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan empty string and it is denoted by λ. The set of all strings (respectively of all non-empty strings) over Vis denoted by V∗(respectively V+). If x, y ∈V∗, then their catenation is xy ∈V∗(the catenation of two strings is the string obtained by the juxtaposition of the two strings, that is, by writing one string after the other one). Catenation is an associative operation and the empty string λacts as an identity: xλ =λx =x, for all x∈V∗. Moreover, for any i≥1, we denote by xi the catenation of icopies of the string x; we set x0=λby definition. The length of a string x∈V∗, denoted by |x|, is the number of all occurrences in xof symbols from V; the number of occurrences in xof a symbol a∈Vis denoted by |x|a. Yet again, by definition, we set |λ|= 0 and |λ|a= 0, for all a∈V. The set of symbols from Voccurring in a string xis denoted by ℵ(x). We also use Vto denote the set of strings from V∗of length equal to 1. Let Vbe an alphabet. A (finite) multiset (over V)is a mapping M:V−→ N, where Ndenotes the set of natural numbers (0 included); for every a∈V,M(a) is called the multiplicity of a(in M). A multiset over Vis usually given in the form of a string over V; each string x∈V∗in fact identifies a multiset Msuch that, for every a∈V,M(a) = |x|a. On the other hand, every multiset Mover Vis representable by means of any string x∈V∗such that, for every a∈V,|x|a=a – the order of the symbols in such a string is not important. Therefore, from this moment on, we will use strings to represent multisets and, given x∈V∗, we will use the expression “multiset x” to refer to a multiset representable by means of string x. Thus, for x∈V∗, for a∈V, the multiplicity of ain xis |x|a, and the size of multiset x(i.e., the sum of all multiplicities) is the value |x|. Moreover, for x, y ∈V∗, we say that multiset xand multiset yare equal, and we write x=y, if, for all a∈V,|x|a=|y|a. We say that multiset xincludes multiset y, and we write xwy, if, for all a∈V, we have |x|a≥ |y|a. If that is the case, we also say that yis included in x, and we write yvx. The union of multiset xand multiset y, denoted by xty, is a multiset wsuch that, for all a∈V,|w|a=|x|a+|y|a. The notion of a rewriting rule between strings can be naturally transferred to multisets. A multiset rewriting rule is a pair (u, v), with u, v two multisets, which is written in the form u→v. Given a multiset wand a rewriting rule u→v, if uvw, then the rule u→vis applicable to the multiset w; if that is the case, the result of the application of the rule u→vto the multiset wis the multiset w0 such that, for all a∈V,|w0|a=|w|a− |u|a+|v|a. If that is case, then we also say that the multiset wcan evolve by means of the multiset rewriting rule u→v. 3 Networks of Cells Here we introduce a general model of membrane systems which allows us to capture the essential features of most variants of cell-like P systems and tissue P systems. Definition 1 (network of cells). Anetwork of cells of degree n≥1(an NC of degree n≥1, for short) is a construct: Π= (V, w1, w2, . . . , wn, R), Networks of Cells and Petri Nets 37 where: 1. Vis an alphabet; 2. wi∈O∗, for all 1≤i≤n, is the multiset initially associated to cell i; 3. Ris a finite set of interaction rules of the form (u1, i1). . . (uk, ik)→(v1, j1). . . (vh, jh) where (a) 1≤k, h ≤n, (b) for all 1≤l, l0≤k,ul∈V+, (c) 1≤il≤nand l6=l0implies il6=il0, (d) for all 1≤r, r0≤h,vr∈V∗,1≤jr≤n, and r6=r0 implies jr6=jr0. A network of cells consists of ncells numbered from 1 to nwith each one of them containing a multiset of objects over V(initially cell icontains multiset wi). Cells can interact with each other by means of the rules in R. An interaction rule of the form (u1, i1)...(uk, ik)→(v1, j1). . . (vh, jh) specifies that, whenever, at the same time, for all 1 ≤l≤k, cell ilcontains at least one occurrence of multiset ul, an occurrence of the multiset ulis consumed inside cell il, for all 1 ≤l≤k, and a multiset vris produced inside cell jr, for all 1 ≤r≤h. In other words, an interaction rule simultaneously rewrites some multisets inside cells i1, . . . , ikin order to produce some new multisets inside cells j1, . . . , jh. Notice also that, for an interaction rule (u1, i1). . . (uk, ik)→(v1, j1). . . (vh, jh), for all 1 ≤l, l0≤k, we have ul∈V+(i.e., a multiset on the left-hand side of the rule cannot be empty) and l6=l0implies il6=il0(i.e., the left-hand side of the rule must involve a set of distinct cells), and, for all 1 ≤r, r0≤h, we have vr∈V∗(i.e., a multiset on the right-hand side of the rule can be empty) and r6=r0implies jr6=jr0(i.e., the right-hand side of the rule must involve a set of distinct cells). For an interaction rule ρof the form (u1, i1). . . (uk, ik)→(v1, j1). . . (vh, jh), cells i1, . . . , ikare called input cells, the set {i1, . . . , ik}is denoted by Input(ρ) and kis called the input radius of ρ; cells j1, . . . , jhare called output cells, the set {j1, . . . , jh}is denoted by Output(ρ) and his called the output radius of ρ; the cooperation degree of ρis the value max{|ui| | 1≤i≤k}; the lefthand side (u1, i1). . . (uk, ik) is denoted by lhs(ρ) whereas the right-hand side (v1, j1)...(vh, jh) is denoted by rhs(ρ). Also, for such a rule ρ, for all 1 ≤i≤n, we use lhsi(ρ) to denote the multiset uif (u, i)∈lhs(ρ), or λif i /∈Input(ρ); we use rhsi(ρ) to denote the multiset vif (v, i)∈rhs(ρ), or λif i /∈Output(ρ). Notice that the structure of an NC corresponds neither to a tree as in cell-like P systems nor to a graph as in tissue P systems (e.g., see [18] for definitions of celllike P systems and tissue P systems), though some models of cell-like P systems and tissue P systems can be seen as special variants of NC’s. The possibility of representing existing variants of P systems as NC’s is illustrated through the following examples. Example 1. A basic P system [18] is defined as a hierarchical arrangement of membranes; each membrane delimits a region which contains a multiset of objects and finite set of evolution rules. If Vis the alphabet of the system, then an evolution 38 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan rule has the form u→(u1, t1)(u2, t2). . . (uq, tq) with u∈V∗, for all 1 ≤r≤q, ur∈V∗and tr∈ {here, out, inj}. If such a rule is associated to a region i, then multiset ucan be replaced by multisets u1, u2, . . . , uqand each multiset uris moved across the membranes depending on the target tr:urremains inside membrane i when tr=here,uris moved outside membrane iwhen tr=out,uris moved into region jwhen tr=injwith ja membrane directly contained into region i. A basic P system can be represented as an NC which has as many cells as the membranes in the P system and which contains, for every region iof the P systems, for every evolution rule u→(u1, t1)(u2, t2). . . (uq, tq) associated to region i, an interaction rule (u, i)→(u1, j1)(u2, j2). . . (uq, jq), with distinct j1, j2, . . . , jq, such that, for all 1 ≤r≤q, if tr=here, then jr=i; if tr=inj, then jr=j; if tr=out, then jris equal to the index of the directly upper region. Example 2. P systems with boundary rules [4] extend basic P systems with rules which allow direct interactions between the inside and the outside of a region. In their most general form (e.g., see [5]), boundary rules are of the form u[iv→u0[iv0 with ithe index of a membrane in the system and u, v, u0, v0∈V∗, for Vthe alphabet of the system. These rules can be represented in NC’s as interactions of the form (u, j)(v, i)→ (u0, j)(v0, i) with jthe membrane which directly contains membrane i. In this way, we can for instance capture the features of symport/antiport rules [18]: •an antiport rule (x, in;y, out) associated to membrane iis no more than an interaction rule (x, j)(y, i)→(y, j)(x, i) with jthe membrane which directly contains membrane i; •a symport rule (x, out) associated to membrane iis no more than an interaction rule (x, i)→(x, j) with jthe membrane which directly contains membrane i; •a symport rule (x, in) associated to membrane iis no more than an interaction rule (x, j)→(x, i) with jthe membrane which directly contains membrane i. Example 3. An evolution-communication model of tissue P systems is proposed in [3] that is based on graphs of cells where each cell contains a multiset of objects and a finite set of rules of the forms x→y(transformation rules) and (x;y, in) (communication rules) with x, y two multisets over a given alphabet. A transformation rule x→yassociated to a cell ispecifies that a multiset xplaced inside cell ican be replaced by a multiset ywhich remains inside cell i. A communication rule (x;y, in) associated to a cell iinstead specifies that, in presence of a multiset x, a multiset ycan be moved from a neighboring cell jnon-deterministically chosen into cell i. Such a tissue P system can be represented as an NC with the same number of cells which contains an interaction rule (x, i)→(y, i), for every transformation rule x→yassociated to cell iof the tissue P system, and a set of interaction rules {(x, i)(y, j)→(xy, j)| {i, j}is an edge of the graph underlying the tissue P system}, for every communication rule (x;y, in) in the tissue P system associated to cell i. Networks of Cells and Petri Nets 39 We now pass to precisely define the execution semantics of networks of cells by identifying different strategies for the application of the rules. To this aim, we first give the following definitions. Definition 2 (configuration). Let Π= (V, w1, w2, . . . , wn, R)be a network of cells. A configuration of Πis any tuple (w0 1, . . . , w0 n)with wi∈O∗, for all 1≤i≤ m. The initial configuration of Πis the tuple (w1, . . . , wn). Definition 3 (multiset of applicable rules). Let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n)be a configuration of Π. A multiset of applicable rules (w.r.t. Πand C)is any function ΓC:R→Nsuch that, for all 1≤i≤n,(Fr∈R(lhsi(r))ΓC(r))vw0 i. Free parallelism Free parallelism means that, in each step, any multiset of applicable rules can be used to make an NC transit from a configuration to another one by applying all the selected rules in parallel at the same time. In membrane computing literature, this semantics is also called asynchronous behavior (e.g., see [9]). Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a freely-parallel way, and we write C⇒free C0, if there is a multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n,w00 i= (w0 i\(Fr∈R(lhsi(r))ΓC(r))) ∪(Fr∈R(rhsi(r))ΓC(r)). Thus, in a freely-parallel step, an arbitrary multiset of applicable rules is selected and these rules are applied in parallel by consuming all the multisets on their left-hand sides and producing all the multisets on their right-hand sides in the respective places. Sequential execution Sequential execution means that, in each step, only one rule is applied to make an NC transit from a configuration to another one. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a sequential way, and we write C⇒seq C0, if C⇒free C0for some multiset of applicable rules ΓCwith |ΓC|= 1. Thus, a sequential step is a freely-parallel step where the number of rules used is equal to 1. Maximal parallelism Maximal parallelism means that, in each step, any maximal multiset of applicable rules can be used to make an NC transit from a configuration to another one by 40 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan applying all the selected rules in parallel at the same time; a maximal multiset of applicable rules is any multiset of applicable rules to which no other rules can be added so to obtain another multiset of applicable rules. Maximal parallelism is the type of behavior which was associated to membrane systems in their original definition [17], and it is the semantics most commonly adopted in the area of membrane computing (e.g., see [1], [18]). Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a maximallyparallel way, and we write C⇒max C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all r∈R, there is 1 ≤i≤nwith lhs(r)i6=λand lhsi(r)6v (w0 i\(Fr∈R(lhsi(r))ΓC(r))). Thus, a maximally-parallel step is a freely-parallel step where rules are applied in parallel in an exhaustive way: once the multisets on the left-hand side of these rules are consumed, no other rule has to be applicable to the objects left inside the cells. Locally-maximal parallelism Locally-maximal parallelism, which was introduced in [13], specifies that, in each step, if a cell is involved in the application of (at least) one rule, then a maximal number of objects are consumed in this cell by applying in parallel as many rules that involve this cell as possible. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Πtransits in one step from configuration Cto configuration C0in a locallymaximally-parallel way, and we write C⇒lmax C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n, if there is r0∈Rwith ΣC(r0)>0 and lhsi(r0)6=λ, then, for all r∈Rwith lhs(r)i6=λ, there is 1 ≤j≤nwith lhs(r)j6=λand lhsj(r)6v (w0 j\(Fr∈R(lhsj(r))ΓC(r))). Thus, a locally-maximally parallel step is a freely-parallel step where if a cell is involved in the application of one rule, then a maximal number of rules involving this cell is applied in parallel at the same time. In other words, in a locallymaximally parallel step, every cell that gets involved tries to participate in as many interactions as possible depending on the objects currently available inside the cell and on the presence of other cells competing for the same objects. Minimal parallelism Minimal parallelism, which was introduced in [6], means that, in each step, every cell that can participate in at least one interaction must get involved in the application of at least one rule. Specifically, let Π= (V, w1, w2, . . . , wn, R) be a network of cells and let C= (w0 1, . . . , w0 n), C0= (w00 1, . . . , w00 n) be two configurations of Π. We say that Networks of Cells and Petri Nets 41 Πtransits in one step from configuration Cto configuration C0in a minimallyparallel way, and we write C⇒min C0, if C⇒free C0for some multiset of applicable rules ΓCsuch that, for all 1 ≤i≤n, if there is no r0∈Rwith ΓC(r0)>0 and lhsi(r0)6=λ, then, for all r∈Rwith lhs(r)i6=λ, there is 1 ≤j≤nwith lhs(r)j6=λand lhsj(r)6v (w0 j\(Fr∈R(lhsj(r))ΓC(r))). Thus, a minimally-parallel step is a freely-parallel step where a maximal number of cells, which are selected depending on the current distribution of objects inside the cells, evolve in parallel at the same time; each one of the selected cells has to participate in at least one interaction, and no other rule has to be applicable in parallel at the same time that involve any cell different from the selected ones. Example 4. Let UNO = (V, aa, aa, bb, c, R) be an NC where Rcontains the following interaction rules: 1. (a, 1) →(a, 1)(a, 2), 2. (a, 1) →(a, 1)(b, 3), 3. (c, 4)(a, 2)(b, 3) →(b, 2)(a, 3), 4. (b, 2) →(b, 2)(c, 4), 5. (c, 4)(b, 3) →(cc, 4)(b, 3), 6. (c, 4)(b, 2) →(bb, 3), 7. (c, 4)(a, 1) →(a, 4)(a, 2)(a, 3). This NC has rules with input radius at most 2 and cooperation degree 1. The initial configuration is given by the tuple C0= (aa, aa, bb, c). To the initial configuration, we can apply rule 1 with multiplicity at most 2, rule 2 with multiplicity at most 2, rule 3 with multiplicity at most 1, rule 5 with multiplicity at most 1, and rule 7 with multiplicity at most 1. However, with respect to C0, it is not possible to apply all these rules in parallel (e.g., only one rule between rules 3, 5 and 7 can be applied because cell 4 contains only one object c). Thus, in the case of free-parallelism, for any configuration C0obtained by applying any combination of the aforementioned rules that is a multiset of applicable rules, we have C0⇒free C0. For instance, if rule 1 is applied with multiplicity 2 and rule 3 is applied with multiplicity 1, we have C0⇒(aa, aaab, ab, λ). In the case of sequential execution, only one of the aforementioned rules is going to be applied with multiplicity 1 to the initial configuration. This gives us five possible transitions: C0⇒seq (aa, aaa, bb, c) when rule 1 is applied, C0⇒seq (aa, aa, bbb, c) when rule 2 is applied, C0⇒seq (aa, ab, ab, λ) when rule 3 is applied, C0⇒seq (aa, aa, bb, cc) when rule 5 is applied and C0⇒seq (a, aaa, abb, a) when rule 7 is applied. If maximal parallelism is adopted, then a maximal number of the aforementioned rules is applied to the initial configuration C0. Specifically, we have the following possibilities: rule 1 (rule 2) applied with multiplicity 2 in parallel with another rule chosen between rules 3 and 5; rule 1 applied in parallel with rule 2 (both with multiplicity 1) together with another rule chosen between rules 3 and 48 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan W((a, 1),2) = 1, W((b, 2),1) = 1, W(2,(b, 1)) = 1, W(2,(a, 2)) = 1, W((b, 2),3) = 1, W(3,(b, 2)) = 2, W(x, y) = 0 in all other cases, and M0= (a, 1)(a, 1)(b, 2)(b, 2). Now, we observe that if F(1) = F(3), then, for the initial configuration C0of DUE,C0⇒lmax (aaaa, bb), but M06;lmax (a, 1)(a, 1)(a, 1)(a, 1)(b, 2)(b, 2). This is because if transition 1 and transition 2 are assigned the same locality, then it is not possible to fire transition 1 with multiplicity 2 without firing in parallel transition 3 with multiplicity 2. This contradicts our hypothesis, hence it has to be F(1) 6=F(3) irrespectively of the value of F(2). Next, if F(1) 6=F(2), then M0;lmax (a, 1)(b, 1)(a, 2)(b, 2)(b, 2) by selecting localities F(2) and F(3), but C06⇒lmax (ab, abb). This is because rule 2 involves cell 1, hence it is not possible to apply rule 2 in parallel with rule 3 without applying at the same time rule 1. Yet again, this contradicts our hypothesis, hence it has to be F(1) = F(2). The same reasoning applies to the case F(2) 6=F(3): M0;lmax (a, 1)(a, 1)(b, 1)(a, 2)(b, 2), but C06⇒lmax (aab, ab). Therefore, it has to be F(1) = F(2) = F(3) but this is in contrast with our earlier observation that it has to be F(1) 6=F(3) in order to have DUE ≡lmax N(DUE, F ). Thus, we can conclude that there is no F:{1,2,3} → Nsuch that DUE ≡lmax N(DUE, F). ut Proposition 5.2 shows that, in the case of locally-maximal parallelism, it is not always possible for the corresponding PTL-net to mimic the behavior of the original network of cells. The intuitive reason for this is that interaction rules may involve several cells at the same time and locally-maximal parallelism for NC’s is defined with respect to the cells involved rather than with respect to the rules applied; localities in PTL-nets are instead associated with transitions and determine which transitions fire in parallel within a step of executions irrespectively of the places involved. However, for an NC with interaction rules of input radius at most 1 (i.e., interaction rules that involve at most one cell in their left-hand side), it is easy to construct a corresponding PTL-net which exhibits an equivalent behavior even for locally-maximally parallelism. This is the case for the basic model of P systems as shown in [13, 12]. A similar result can be obtained for minimal parallelism. Proposition 5.3 There exists a network of cells Πwith 3rules such that, for all F:{1,2,3} → N, we have that Π6≡min N(Π, F). Proof. Let DUE = ({a, b}, aa, bb, R) be the NC used in the proof of Proposition 5.2 with its initial configuration C0= (aa, bb) . Then, let us suppose that DUE ≡m N(DUE, F) for some F:{1,2,3} → N. PTL-net N(DUE, F ) is the same as the one defined in the proof of Proposition 5.2. Now, we observe that if F(1) = F(2) = F(3), then, by firing only transition 1 with multiplicity 1, M0;min (a, 1)(a, 1)(a, 1)(b, 2)(b, 2), but C06⇒min (aaa, bb). This is because rule 1 involves only cell 1, hence, since we are operating according to the minimal parallelism, it is not possible to apply rule 1 with multiplicity 1 without applying in parallel at the same time at least another rule involving cell 2. This contradicts our hypothesis, hence it cannot be F(1) = F(2) = F(3). Networks of Cells and Petri Nets 49 Next, if F(1) 6=F(2), then, by applying rule 2 with multiplicity 1, C0⇒min (ab, ab) but M06;min (a, 1)(b, 1)(a, 2)(b, 2). This is because, since we are operating according to minimal parallelism, it is not possible to fire transition 2 with multiplicity 1 without firing in parallel at the same time at least another transition belonging to locality F(1) 6=F(2). The same reasoning apply to case F(2) 6=F(3). Therefore, it has to be F(1) = F(2) and F(2) = F(3) but this is in contrast with our earlier observation that it cannot be F(1) = F(2) = F(3) in order to have DUE ≡min N(DUE, F). Thus, we can conclude that there is no F:{1,2,3} → Nsuch that DUE ≡min N(DUE, F). ut Proposition 5.3 shows that, even for minimal parallelism, it is not always possible for the corresponding PTL-net to mimic the behavior of the original network of cells. Proposition 5.2 and Proposition 5.3 are both based on the fact that an NC may contain both rules of input radius 1 with a local scope and rules of radius greater than 1 which in a sense belong to different cells at the same time. We pass now to consider the reverse problem of finding for every PTL-net a corresponding network of cells with an equivalent behavior. Definition 14. Let N= (P, T, W, M0, L)be a PTL-net. 1. A cell mapping for Nis any surjective function C:P→ {1, . . . , n}with n≥1. 2. For all t∈T, for any cell mapping Cfor N, the pre-partition of t(w.r.t. C), denoted by prepC(t), is the string (w1, c1)(w2, c2)...(wk, ck)such that preN(t) = w1w2. . . wk, for all 1≤i≤k,wi6=λand C(ℵ(wi)) = {ci}, and, for all 1≤i, j ≤kwith i6=j,C(ℵ(wi)) 6=C(ℵ(wj)). 3. For all t∈T, for any cell mapping Cfor N, the post-partition of t(w.r.t. C), denoted by postpC(t), is the string (w1, c1)(w2, c2)...(wk, ck)such that postN(t) = w1w2. . . wk, for all 1≤i≤k,wi6=λand C(ℵ(wi)) = {ci}, and, for all 1≤i, j ≤kwith i6=j,C(ℵ(wi)) 6=C(ℵ(wj)). 4. For every marking Mof N, for any cell mapping Cfor N, the partition of M (w.r.t. C), denoted by partC(M), is the string (w1, c1)(w2, c2). . . (wk, ck)such that M=w1w2. . . wk, for all 1≤i≤k,wi6=λand C(ℵ(wi)) = {ci}, and, for all 1≤i, j ≤kwith i6=j,C(ℵ(wi)) 6=C(ℵ(wj)). 5. For every marking Mof N, for any cell mapping C:P→ {1, . . . , n} for N, the extended partition of M(w.r.t. C), denoted by expC(M), is the tuple (w1, w2, . . . , wn)such that M=w1w2. . . wnwith partC(M) = (wc1, c1)(wc2, c2). . . (wck, ck)for some {c1, c2, . . . , ck} ⊆ {1,2...,n}and wi= λfor all i6∈ {c1, c2, . . . , ck}. Thus, given a network of cells N, we use the cell mapping to associate places to certain cells and we use the concept of partition to distribute the places (i.e., their multiple occurrences) to these cells. Specifically, we give the following definition. Definition 15 (corresponding NC). Let N= (P, T, W, M0, L)be a PTL- net and let C:P→ {1, . . . , n}be a cell mapping for N. The network of 50 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan cells corresponding to N(w.r.t. C)is P(N, C)=(P, w1, w2, . . . , wn, R)where: expC(M0) = (w1, w2, . . . , wn)and R={(u1, i1)...(uk, ik)→(v1, j1). . . (vh, jh)| t∈T, prepC(t) = (u1, i1)...(uk, ik), postpC(t) = (v1, j1). . . (vh, jh)}. Thus, we can construct different NC’s corresponding to the same PTL-net depending on the way we decide to assign places to cells; the unique constraint is that multiple occurrences of the same place have to remain confined within the same cell. At one end, a PTL-net can be translated into an NC with one cell where all the rules have input radius equal 1; every rule corresponds to a transition and these rules are no more than multiset rewriting rules. At the opposite end, a PTL-net can be translated into an NC with as many cells as its places; every rule corresponds to a transition and the its input radius is equal to the cardinality of the support of the pre-multiset of this transition. Notice that the locality mapping of a PT-net has no direct counterpart in the corresponding NC’s. Next, we introduce the notion of equivalence between a PTL-net and its corresponding NC’s. Definition 16 (m-equivalence). Let N= (P, T, W, M0, L)be a PTL-net and let C:P→ {1, . . . , n}be a cell mapping for N. For m∈ {free, seq, max, lmax, min}, we say that Nis m-equivalent to P(N, C), and we write N≈mP(N, C)if, for every two markings M1, M2,M1;mM2iff expC(M1)⇒mexpCM2. Thus, we can state the fundamental property which relates PTL-nets and corresponding NC’s. Proposition 5.4 For any PTL-net N= (P, T, W, M0, L), for any cell mapping Cfor N, for m∈ {free, seq, max}, we have that N≈mP(N, C). Moreover, if L(T) = {l}for some l≥0, then, for any cell mapping Cfor N, for m∈ {lmax, min}, we have that N≈mP(N, C). Therefore, the general equivalence between a PTL-net and its corresponding NC’s can only be established for free-parallelism, sequential execution and maximal parallelism. For locally-maximal parallelism and minimal parallelism, the aforementioned equivalence can be established only for PTL-nets where all transitions are assigned to the same locality. In fact, the following results holds. Proposition 5.5 There exists a PTL-net Nsuch that, for any cell mapping C for N, for m∈ {lmax, min}, we have that N6≈mP(N, C). Proof. Let NONE be the PTL-net of Figure 2 where: transition Ris assigned locality 1, transition Sis assigned locality 2, and transition Tis assigned locality 2; the initial marking of NONE is M0=aabb. Then, let us suppose that there is a cell mapping Cfor NONE such that NONE ≈mP(NONE, C). Now, if C({a, b}={1}(i.e., if P(NONE, C) contains only one cell), then it is obvious that NONE 6≈mP(NONE, C). Therefore, it has to be C({a, b}={1,2} Networks of Cells and Petri Nets 51 (i.e., P(NONE, C) has to contain two cells) in order to be able to distinguish between locality 1 and 2. Then, if C(a) = 1 and C(b) = 2, then, by Definition 15, P(NONE, C) contains rules: (a, 1) →(aa, 1), (a, 1)(b, 2) →(b, 2), and (b, 2) →(bb, 2). Thus, M0;lmax aabb by firing transition Rand transition Sbelonging to the same locality, but expC(M0) = (aa, bb)6⇒lmax (aa, bb). This is because rule (a, 1)(b, 2) →(b, 2) involve cell 1 as well as cell 2, hence we cannot apply rule (a, 1) →(aa, 1) in parallel with rule (a, 1)(b, 2) →(b, 2) without applying at the same time rule (b, 2) →(bb, 2). This contradicts our hypothesis. For symmetry, the same reasoning apply to the case C(a) = 2 and C(b) = 1. Therefore, we can conclude that, for any cell mapping Cfor N, we have that N6≈lmax P(N, C). For a minimally-parallel execution, it is easy to go through the same cases as above and verify that, for any cell mapping Cfor N, we have that N6≈min P(N, C). ut Fig. 2. PTL-net N ON E with its initial marking where transition Ris assigned to locality 1, transition Sis assigned to locality 2, and transition Tis assigned to locality 2. Finally, we stress once more the differences between cells and places. Cells of an NC are bags of objects that can contain multiple occurrences of different symbols, each one of them representing a different sort of objects; cells are seen as distinct components of a larger system whose behavior is given by their interactions; the adopted semantics determines which and how many cells become active from time to time. Places of a PTL-net store a number of tokens, each one of them representing a distinct occurrence of a specific place; places with their number of tokens represent resources that have to be acquired by transitions in order to fire, and, in PTL-nets, one usually abstracts from the actual location of these resources. Therefore, when translating a PTL-net into an NC, one has to make some extra assumptions about the assignment of places to cells, although, in general, one can 52 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan always see a PTL-net as an NC with one cell containing a finite set of multisets of rewriting rules. 6 Case-Studies We present NC’s solutions to two classical synchronization problems: producer/consumer and dining philosophers. The proposed models are derived from standard solutions based on Petri Nets. 6.1 Producer/Consumer We consider the simpler version of the producer/consumer system from [20]: distinguished items are produced, delivered to a buffer, later removed from the buffer, and finally consumed. The buffer is assumed to have capacity for one item. Moreover, like in [20], we abstract from any concrete instance of the aforementioned operations and we focus only on the “interplay” between produce/deliver and remove/consume, and on the events necessary for their synchronization. Specifically, we consider two sub-systems named producer and consumer, respectively, which “synchronize” (or “interact”, or “communicate”) through a shared buffer. The producer has two states: “ready to produce” and “ready to deliver”. The consumer has two states: “ready to remove” and “ready to consume”. The buffer has two states: “filled” and “empty”. In state “ready to produce”, the producer executes the operation “produce” and moves to state “ready to deliver”; in state “ready to produce”, if the buffer is “empty”, the producer executes the operation “deliver”, which fills the buffer, and moves back to state “ready to produce”. Similarly, in state “ready to remove”, if the buffer is “empty”, the consumer execute the operation “remove”, which empties the buffer, and moves to state “ready to consume”; in state “ready to consume”, the consumer executes the operation “consume” and moves back to state “ready to remove”. PTL-Net Representation The PTL-net model of the aforementioned producer/consumer system, which is presented in [20], is reported in Figure 3, with its initial marking AEG, where: A≡“ready to produce”, B≡“ready to deliver”, F≡“filled”, E≡“empty”, G≡“ready to remove”, H≡“ready to consume”, p≡“produce”, d≡“deliver”, Networks of Cells and Petri Nets 53 Fig. 3. PTL-net model of a producer/consumer system. r≡“remove”, c≡“consume”. The unique transition enabled at the initial marking AEG is transition p(“produce”), and, when fired, it transfers a token from place A(“ready to produce”) to place B(“ready to deliver”). Next, transition d(“deliver”) is enabled and, when fired, it produces a token in place F(i.e., the buffer is filled) and a token in place A(“ready to produce”). Then, transition r(“remove”) can fire which produces a token in place E(i.e., the buffer is emptied) and a token in place H(“ready to consume”). Finally, a token can be returned to place G(“ready to remove”) by firing transition c(“consume”). We remark that: •seq-execution and free-execution are non-deterministic; after transition dhas fired, both transition p and transition rare enabled and, after transition rhas fired, both transition dand transition care enabled; •max-execution is deterministic; •if transitions pand dare assigned to a certain locality (i.e., the producer) and transition rand cto another one (i.e., the consumer), then lmax-execution is equivalent to free-execution; •if transitions pand dare assigned to a certain locality (i.e., the producer) and transition rand cto another one (i.e., the consumer), then min-execution is equivalent to max-execution; •irrespectively of the semantics, in each step, at least one transition is always enabled (liveness); •irrespectively of the semantics, the consumer can consume only after having received an item from the buffer (i.e., only after having performed a “remove” operation); •irrespectively of the semantics, after having produced an item, the producer has to deliver it into the buffer before returning to producer; the delivering can take place only when the buffer has been emptied. 54 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan NC Representation As pointed out in Section 5, it is possible to find different NC’s corresponding to the PTL-net of Figure 3. Here, in order to model the aforementioned producer/consumer system, we consider an NC PC with 3 cells. Cell 1 represents the producer, cell 2 represents the consumer, whereas cell 3 represents the buffer. Cell 1 stores an object which specifies the states of the producer; this can be either A(“ready to produce”) or B(“ready to deliver”). Similarly, cell 2 stores an object which specifies the state of the consumer; this can be either G(“ready to remove”) or H(“ready to consume”). Cell 3 instead stores an object representing the state of the buffer, either F(“filled”) or E(“empty”). The initial configuration is the tuple (A, G, E). The desired behavior is then implemented by considering the following rules: 1. (A, 1) →(B, 1), 2. (B, 1)(E, 2) →(A, 1)(F, 3), 3. (G, 2)(F, 3) →(H, 2)(E, 3), 4. (H, 2) →(G, 2). Yet again, we have that: •the application of the rules is sequential and freely-parallel; •the maximally-parallelism is deterministic; •irrespectively of the semantics, in each step, at least one rule is always applicable; •irrespectively of the semantics, the consumer can consume only after having received an item from the buffer; •irrespectively of the semantics, after having produced an item, the producer has to deliver it into the buffer before returning to producer; the delivering can take place only when the buffer has been emptied. Also, the PT-net N(PC) is the same as the PTL-net of Figure 3 except for the naming of places and transitions (i.e., they define two isomorphic graphs). In fact, rule 1 corresponds to transition pin the PT-net of Figure 3, rule 2 corresponds to transition din the PT-net of Figure 3, rule 3 corresponds to transition rin the PT-net of Figure 3, and rule 4 corresponds to transition cin the PT-net of Figure 3. Moreover, for F:{1,2,3,4} → Nsuch that F(1) = F(2), F(3) = F(4) and F(1) 6=F(3), we have that P C ≡lmax N(PC, F) and PC ≡min N(PC, F). The vice versa is also true: for the PTL-net of Figure 3, if transitions pand dare assigned to a certain locality (i.e., the producer) and transition rand c to another one (i.e., the consumer), then, for m ∈ {free, seq, max, lmax, min}, PTL-net of Figure 3 is m-equivalent to PC. Therefore, for this version of the producer/consumer system, there is a sort of direct transcription of the PTL-net model into an NC model whose rules are able to represent exactly the same type of interactions between a producer and a consumer. Networks of Cells and Petri Nets 55 Remark 4. For the present version of producer/consumer, the fundamental properties are: there is always a transition enabled (liveness), the producer always alternates between “ready to consume” and “ready to deliver”, and the consumer always alternates between “ready to remove” and “ready to consume”. These properties are formally proved in [20] for the PTL-net of Figure 3 and these results can be directly transferred to our NC model; at some extent, this gives a flavor of the sort of properties which could be proved for NC’s (or any other membrane systems) by using techniques developed in the area of Petri nets. Next, we describe an evolution-communication model of the producer/consumer systems that is not a direct translation of the PTL-net solution from [20] but is inspired by the idea of P systems as systems where transformations involve only objects inside one specific cell and communication is responsible for moving objects from one cell to the other. In other words, we consider an NC with interaction rules of input radius 1 which does not rely on the simultaneous synchronization of two different cells. Similarly to what was done before, we consider an NC PC1 with 3 cells: cell 1, the producer, cell 2, the consumer, and cell 3, the buffer. The initial configuration of PC1 is the tuple (A, G, E). Cell 1 always moves from state A(“ready to produce”) to B(“ready to deliver”) by replacing in its inside object Awith object B. In state B, after having received an object Efrom cell 3 (i.e., after having been notified that the buffer is empty), cell 3 produce in its inside an object Aand object F; object Fis then sent to cell 3 to fill the buffer. In state G(“ready to remove”), cell 2 always waits to receive an object Ffrom cell 3 in order produce in its inside an object H (representing state “ready to consume”) and an object E; object Eis then sent to cell 3 to notify that the buffer is now empty. This behavior is implemented by means of the following rules: 1. (A, 1) →(B, 1), 2. (E, 3) →(E, 1), 3. (BE, 2) →(AF, 1), 4. (F, 1) →(F, 3), 5. (F, 3) →(F, 2), 6. (GF, 2) →(HE, 2), 7. (H, 2) →(G, 2), 8. (E, 2) →(E, 3). Thus, all these rule have input radius equal to 1 and interactions between cell 1 (cell 2) are achieved through an effective exchange of objects. However, irrespectively of the semantics adopted, the aforementioned fundamental properties can still be observed: at any time, at least one rule is applicable, the producer always alternates between “ready to consume” and “ready to deliver”, and the consumer always alternates between “ready to remove” and “ready to consume”. Moreover, the producer can deliver only when the buffer is empty, and the consumer can 56 F. Bernardini, M. Gheorghe, M. Margenstern, S. Verlan remove only when the buffer is filled. Also, notice that PC1 is somehow “more concurrent” than PC: there is always some communication which can be executed in parallel with the internal change of state. Nevertheless, maximal parallelism still leads to a deterministic behavior for PC1 and the movement of objects Eand F does not affect the behavior of producer and consumer. PTL-net N(PC1) is given in Figure 4. Fig. 4. PTL-net N(P C1) with its initial marking. Remark 5. The solution based on the NC PC uses rules of input radius at most 2 and cooperation degree at most 1, whereas the solution based on the PC1 uses rules of input radius at most 1 and cooperation degree at most 2. In some sense, this shows a trade-off between the cooperation at level of cells and the cooperation at the level of objects. Remark 6. If we do not consider the names of places and transitions, the PTL-net of Figure 4 is the same as the PTL-net of Figure 3 excepts for the presence of some “unary” transitions which correspond to the movement of objects Eand F between cell 1, cell 2 and cell 3. Indeed, by using standard structural methods of Petri nets (e.g., see [11]), the aforementioned transitions could be removed so to have a PTL-net which is the same as the one of Figure 3 and inherits the same structural properties proved in [20]. Thus, the translation into PTL-net allows us to relate two different models of NC’s in terms of structural properties which are somehow hidden in the two different types of rules used. 7 Dining Philosophers We consider a distributed system where each resource is shared by two components, and each subsystem simultaneously requires two resources in order to start its Networks of Cells and Petri Nets 57 activities. The problem of modeling such a resource sharing scenario is classically formulated as the problem of the dining philosophers: five philosophers are sitting around a table, each philosopher has his own plate and can be eating or thinking (i.e., not eating). In order to eat, a philosopher needs two forks, but there are only two forks next to each plate so that no two neighboring philosophers may be eating simultaneously. PTL-net representation The five philosophers are denoted by A,B,C,Dand E; the five forks are denoted by f0,f1,f2,f3and f4. For each X∈ {A, B, C, D, E}, we denote by l(X) its left fork and by r(X) its right fork. Specifically, we set: l(A) = f0,r(A) = f1, l(B) = f1,r(B) = f2,l(C) = f2,r(C) = f3,l(D) = f3,r(D) = f4,l(E) = f4and r(E) = f0(i.e. Asits between Eand B,Bsits between Aand C,Csits between Band D,Dsits between Cand E, and Esits between Dand A). Thus, a PTL-net FDP is constructed that contains: for each X∈ {A, B, C, D, E}, a place Xt(“Xtis thinking”) and a place Xe(“Xeis eating”), for each 0 ≤i≤4, a place fi(“fiis available”), for each X∈ {A, B, C, D, E}, a transition Xp(“Xpicks up forks”) with preF DP (Xp) = l(X)Xtr(X) and postF DP (Xp) = Xe, and a transition Xr(“Xreturns forks”) with preF DP (Xr) = Xeand postF DP (Xr) = l(X)Xtr(X). The initial marking of FDP is AtBtCtDtEtf0f1f2f3f4(i.e., all philosophers are thinking and all forks are available). Figure 5 depicts the sub-net of an FDP modeling a philosopher. This classical PTL-net model of the dining philosophers is taken from [20]. At the initial marking AtBtCtDtEtf0f1f2f3f4, for X∈ {A, B, C, D, E}, each transition Xp(“Xpicks up forks”) is enabled by giving all philosophers a chance to start eating. However, irrespectively of the execution mode adopted, no two neighboring philosophers can start eating at the same time because they share one fork and, for all 0 ≤i≤4, ficontains only one token. Thus, in the first step, depending on the execution mode, a certain number of philosophers which are not neighbors start eating by firing at least one transition Xp, whereas the other philosophers keep thinking. Then, depending on the execution mode, some other philosophers may start eating, whereas the eating philosophers may release their forks and return thinking, and so on. The fundamental property of the PTL-net FDP is that it avoids the deadlocks: FDP never produces a marking which no transition is enabled at. Moreover, from time to time, FDP offers every philosopher the chance to start eating (i.e., it avoids scenarios where no philosopher can ever start eating), although fairness is not guaranteed (i.e., there may be some philosophers which always alternate between thinking and eating with the other philosophers thinking indefinitely). Yet again, this structural properties are formally proven in [20].