A Membrane Computing Model for Ballistic Depositions

A Membrane Computing Model for Ballistic Depositions Carmen Graciani-Díaz, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez Research Group on Natural Computing University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain {cgdiaz,magutier,marper}@us.es Summary. Ballistic Deposition was proposed by Vold [9] and Sutherland [8] as a model for colloidal aggregation. These early works were later extended to simulate the process of vapor deposition. In general, Ballistic Deposition models involve (d+ 1) -dimensional particles which rain down sequentially at random onto a d -dimensional substrate; when a particle arrives on the existing agglomeration of deposited particles, it sticks to the rst particle it contacts, which may result in lateral growth. In this paper we present a rst P system model for Ballistic Deposition with d= 1 . 1 Introduction Some recent discoveries on the dynamical process of surface growth have encouraged the scientic community to revisit the study of systems exhibiting rough interfaces. In Nature, there exist many examples of rough interfaces, actually, all surfaces in Nature can be seen as rough surfaces, since the concept of roughness is associated to the scale of observation and surfaces on Nature are far from be smooth if observed at appropriate scale. The propagation of forest res [5], the growth of a colony of bacteria [3] or the propagation of reaction fronts in catalyzed reactions [1] are real-world examples where the frontier between two media are far from being smooth. In this cases, the interfaces can be hardly modeled with Euclidean geometry and it is necessary to consider new tools in order to handle them. Moreover, in that cases, we are interested not only in the morphology of the interfaces from a static point of view, but in the dynamics of how the interface develops in time. These dynamics can be studied from two complementary approaches: • Discrete approaches where the position of each particle of the surface is well dened. This approach is getting more consideration at the atomic level in the last years due to the use of new technology as the scanning tunneling microscopy, capable of identifying not only the structure of the lattice of particles, but the position of individual atoms as well. 180 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez A B A0 B0 ? ? Fig. 1. Ballistic Deposition • Continuum approaches view the surface on a coarse-grained scale, in which every property is averaged over a small volume containing many atoms. Their predictive power is limited to length scales larger than the typical inter-atom distance. This paper is devoted to the study of a process of formation of rough surfaces called Ballistic Deposition (BD). To this aim, we will explore the capability of some Membrane Computing devices as tools for modeling BD in a discrete approach. The paper is organized as follows: rst the Ballistic Deposition model is briey described. In Section 3, deposition P systems are presented and following this model, a P system simulating the dynamics of Ballistic Deposition is presented in Section 4. Some conclusions are presented in Section 5. The paper ends with the Bibliography and an Appendix with the proof of our main result. 2 Ballistic Deposition In Nature, some interfaces are formed as result of a deposition process, other shrink due to erosion. A typical example of deposition process is the random fall of snowakes on the ground oor. The randomness in the deposition process leads to a rough surface. There exist many deposition models which try to represent dierent natural process. The simplest way to dene such models is on a lattice where particles are deposited onto a surface oriented perpendicular to the particle trajectories, but other versions have been also investigated 1 . Ballistic Deposition (BD) was proposed by Vold [9] and Sutherland [8] as a model for colloidal aggregation. These early works were later extended to simulate the process of vapor deposition. In this model, a particle is released from a position above the surface. The particle follows a straight vertical trajectory until it reaches the surface, whereupon it sticks (see Figure 1). 1 A good starting point for the study of depositions is [2]. A Membrane Computing Model for Ballistic Depositions 181 In general, Ballistic Deposition models involve (d+ 1) -dimensional particles which rain down sequentially at random onto a d -dimensional substrate; when a particle arrives on the existing agglomeration of deposited particles, it sticks to the rst particle it contacts, which may result in lateral growth. Many mathematical models exist in order to describe Ballistic Depositions. Here we follow M.D. Penrose in [6], where all particles are assumed identical is presented. In Penrose's mathematical model, the substrate is Rd×{0} , identied with Rd or some subregion thereof. All particles are (d+ 1) -dimensional solids. Particles arrive sequentially at random positions in Rd . When a particle arrives at a position x∈Rd , it slides down the ray {x}×[0,∞) until the particle hits a position adjacent to either the substrate or a previously deposited particle where is permanently xed. The dierence between lattice and continuum models is that in the lattice model the positions at which particle arrive are restricted to be in the integer lattice Zd . Let 0 denote the origin in Zd . A displacement function is a mapping D:Zd→ [−∞,∞) verifying: •D(0) = 1 • The set N={x∈Zd:D(x)6=−∞} is nite but has at least two elements (one of which is the origin) For z∈Zd , let Nx={x+y:y∈ N} and N∗ x={x−y:y∈ N} . The set N is a neighborhood of the origin and Nx is a neighborhood of x . The idea of a displacement function is that if a particle arrives at y∈ Nx then it cannot slide down the ray y×[0,+∞) below the position at height D(y−x) . In this way, if h(x, t) measures the height of the interface at site x at time t then h(x, t + 1) = max{h(y, t) + D(x−y) : y∈Zd} since −∞ +x=−∞ for all x∈R then h(x, t + 1) = max{h(y, t) + D(x−y) : y∈ N ∗ x} In this paper we follow the version of ballistic deposition considered in [7], the nearest neighbor model, where N={z∈Zd:kzk1≤1} and the displacement function D is given by D(x) = 0 for x∈ N − {0} . We are considering that the dimension of the substrate is d= 1 and therefore h(x, t + 1) = max{h(y, t) + D(x−y) : y∈ N∗ x} =max{h(y, t) + D(x−y) : y∈ {x−1, x, x + 1}} =max{h(x−1, t) + D(1), h(x, t) + D(0), h(x+ 1, t) + D(−1)} =max{h(x−1, t)+0, h(x, t)+1, h(x+ 1, t)+0} =max{h(x−1, t), h(x, t)+1, h(x+ 1, t)} 182 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez 3 P systems The chosen P systems model can be considered a subclass of tissue-like P system, since we do not consider membranes surrounding other ones, but a sequence of cells linked by communication channels. The intuition behind this structure is that each cell represent a column of the aggregate and the pieces of information needed for encoding the growth process are encoded on the multisets of objects in the cells. In this model we use two very powerful membrane computing tools: the cooperation and the use of polarizations of the cells. Both features allow us an ecient design of P systems in order to perform the simulation. The study of minimal resources, i.e., to know whether the deposition process can be simulated without some of the used ingredients falls out of the scope of this paper. Formally, a deposition P system of degree L is a construct of the form Π= (O, µ, env, v1, . . . , vL, venv, P, R) where: 1. O is the alphabet of objects; 2. µ is a cell structure consisting of L cells bijectively labelled with {1, . . . , L} . For all i∈ {1, . . . , L −1} there exist an edge between the cell i and the cell i+ 1 . We will also consider an edge between the cell L and the cell 1 . For the sake of simplicity, we will identify the indices L+ 1 and 1 ; also, if a cell has polarization 0 , we will omit the symbol 0 . 3. env is the environment. It represents the region surrounding the cell structure µ . Some objects can be also placed in this region. 4. v1, . . . , vL, venv are strings over O , describing the multisets of objects placed in the corresponding cells of µ or in the environment. 5. P={0,+,−} is the set of polarizations. 6. R is a nite set of rules , of the following forms: a) [v1→v2]e i where i∈ {1, . . . , L} , e∈P and v1, v2 are strings over O describing multisets of objects. These are object evolution rules associated with cells and depending only on the label and the polarization of the cell. The string v1 has at least one object. b) a[ ]e1 i→[b]e2 i where i∈ {1, . . . , L} , e1, e2∈P and a, b ∈O . These are send-in rules . An object of the environment is introduced in the membrane possibly modied. The polarization of the cell can also change. c) [a]e1 i→b[ ]e2 i where i∈ {1, . . . , L} , e1, e2∈P and a, b ∈O . These are sendout rules . An object is sent out to the environment possibly modied. The polarization of the cell can also change. d) [a]e1 i,[ ]i+1 →[ ]i,[b]e2 i+1 [ ]i,[a]e1 i+1 →[b]e2 i,[ ]i+1 where i∈ {1, . . . , L} , e1, e2∈P and a, b ∈O . These are communication rules . An object a is sent, possibly modied, to a contiguous cell. Rules are applied according to the following principles: A Membrane Computing Model for Ballistic Depositions 183 • Rules are used as usual in the framework of membrane computing, that is, in a maximal parallel way. In one step, each object in a cell can only be used for one rule (non deterministically chosen when there are several possibilities), but any object which can evolve by a rule of any form must do it. with a restriction, only one change of polarization can aect to a membrane. • All the elements which are not involved in any of the operations to be applied remain unchanged. • Several rules can be applied to dierent objects in the same cell simultaneously. • If any rule of type (a) are used at the same time that one of type (b), (c) or (d), all rules are applied, but we will consider that the object evolution rules (a) are performed before the other one. This consideration is useful because the rule that sends an object across a membrane can also changes its polarization. 4 Modeling BD In this section we will consider a BD system with L columns and we will provide a deposition P system which simulates its dynamics. Let us consider the deposition P systems of degree L , Π= (O, µ, env, v1, . . . , vL, venv, P, R) where: •O={p, c0, c1, c2, c3, c4, c5, c6, cn3, cn4, α, x, y, z} •vi=∅ , for all i∈ {1, . . . , L} •venv =p Let us consider the following sets of rules, where the index i∈ {1, . . . , L} . As remarked before, we will identify the indices L+ 1 and 1 and the indices 0 and L ; and, if a cell has polarization 0 , we will omit the symbol 0 . Set (A)  Deposition rules: Ri ∗≡p[ ]i→[c0]+ i In the BD model, a particle is deposited on the top of a column randomly chosen. We simulate this process by these rules. A particle p in the environment is sent to one of the cells. This particle activates the cell (the polarization of the cells turns on positive) and goes into the cell as the object c0 . Set (B)  Rules for cells with positive polarization: Ri 1≡[c0→c1]+ iRi 4≡[ ]i,[c2]+ i+1 →[cn3]− i,[ ]i+1 Ri 2≡[c1→c2]+ iRi 5≡[ ]i,[z]+ i+1 →[y]i,[ ]i+1 Ri 3≡[y→z α]+ i The sets Ri 1 , Ri 2 and Ri 3 are object evolution rules and Ri 4 and Ri 5 are communication rules. Note that the counter ck sent into a cell i , by the particle p gives two waiting step before being sent to the cell i−1 transformed into cn3 (by the rule Ri−1 4 ). These waiting steps check the occurrence of objects y inside the cell. If any y occur, each of then evolves to z α at the same time in which c0 evolves to c1 and 184 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez in the following step each z is sent to the cell i−1 transformed into y and the polarization of the cell i changes. If this happens, the rule Ri−1 4 is not triggered because the cell containing c2 has not positive charge. Set (C)  Rules for cells with negative polarization: Ri 6≡[c3→c4]− iRi 10 ≡[cn3→cn4]− i Ri 7≡[c4→c5]− iRi 11 ≡[cn4→x y c5]− i Ri 8≡[c5→c6]− iRi 12 ≡[x]− i,[ ]i+1 →[ ]i,[z]i+1 Ri 9≡[c6]− i→p[ ]i The sets Ri 6 , Ri 7 , Ri 8 , Ri 10 and Ri 11 are object evolution rules, Ri 12 are communication rules and Ri 9 are send-out rules. The counter ck goes on with the objects c3 and c4 or with cn3 and cn4 . In both cases, the counter reaches c5 and c6 . The object c6 sends to the environment an object p which will go into a cell in the next step according to the set of rules Ri ∗ . Set (D)  Rules for cells with polarization zero: Ri 13 ≡[cn4→c5]iRi 16 ≡[z→x α]i Ri 14 ≡[c5→c6]iRi 17 ≡[x y →λ]i Ri 15 ≡[c6]i→p[ ]iRi 18 ≡[ ]i,[c2]i+1 →[c3]− i,[ ]i+1 The sets Ri 13 , Ri 14 , Ri 16 , and Ri 17 are object evolution rules, Ri 18 are communication rules and Ri 15 are send-out rules. As in the set of rule (B) , the counter ck goes on till it reaches c6 . The object c6 sends to the environment an object p which will go into a cell in the next step according to the set of rules Ri ∗ . Notice that rules of Ri 17 are cooperative rules. Each pair of objects hx, yi which occur in a cell disappears in the next step. 4.1 Informal description of the computation For a better understanding of the computation, let us remark that the congurations at time 8t with t∈N represent the state of a BD system after the deposition of the t -th particle. Below we will formalize this idea, but before giving a description of the computation, we provide the intuitive meaning of some of the symbols of the alphabet at time 8t : •p represents the particle that arrives to the substrate. When it is deposited, it disappears from the environment, then the information encoded in the cells change. When the computation inside the cells nishes, a new particle is sent to the environment and the process starts again. In this way only in the steps 8t , there exists a particle p in the environment. • The multiplicity of α in the cell i represent the height of the column i in the BD model. A Membrane Computing Model for Ballistic Depositions 185 Time Rules Env. Conguration T0p1 2 3 4 T1R3 ∗1 2 c0 + 34 T2R3 11 2 c1 + 34 T3R3 21 2 c2 + 34 T4R2 41cn3 − 23 4 T5R2 10 1cn4 − 23 4 T6R2 11 1x y c5 − 23 4 T7R2 8, R2 12 1y c6 2 z3 4 T8R2 15, R3 16 p1y2x α 3 4 Fig. 2. Table with the rst steps Finally, the remaining objects inside the cells at time 8t are of type x and y . The objects x or y inside the cell i represent the dierence of height between the cell i and the cell i+ 1 . • The multiplicity of x in the cell i represent how many units is the column i higher than column i+ 1 in the BD model. • The multiplicity of y in the cell i represent how many units is the column i lower than column i+ 1 in the BD model. From the previous description we have that at time 8t , we can nd inside a cell objects x , y or none of them, but we will never nd both simultaneously. Tables 2 and 3 show an example of evolution of a simple BD system with four columns where four particles have been deposited sequentially on the columns 3, 2, 2 and 1. Notice that the congurations at times 8t with t∈ {0, . . . , 4} represent the surface of the BD model after the fall of the t -th particle (Fig. 4). We nish this section by formally showing that this deposition P system of degree L simulates the ballistic deposition on a substrate with L columns. In this way we need the denition of representative conguration . The idea behind the 186 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez Time Rules Env. Conguration T9R2 ∗1y c0 + 2x α 3 4 T10 R1 2, R2 31z α c1 + 2x α 3 4 T11 R2 2, R1 5y1α c2 2 x α 3 4 T12 R1 18 y c3 − 1α2x α 3 4 T13 R1 6y c4 − 1α2x α 3 4 T14 R1 7y c5 − 1α2x α 3 4 T15 R1 8y c6 − 1α2x α 3 4 T16 R1 9p y 1α2x α 3 4 ... ... ... ... 1 ... 2 ... 3 ... 4 T24 ... p y21x α22α x 3 4 ... ... ... ... 1 ... 2 ... 3 ... 4 T32 ... p α21x α22x α 3y24 Fig. 3. Table with the rst steps (Cont.) denition is quite intuitive. Along the computation, some of the congurations have no meaning with respect to the deposition process, there are merely auxiliary steps of the computation. Only some of the conguration represent states of the aggregate in the deposition process. Such congurations will be called representative congurations We will denote by Ct the conguration of the P systems at time t , by Ct(i) the multiset of objects at the cell labelled by i at time t and by |Ct(i)|a the multiplicity of the object a in Ct(i) . Denition 1. Let Ct be a conguration of a deposition P systems of degree L at time t . We will say that Ct is representative if for all i∈ {1, . . . , L} , • Only objects α , x and y occur inside the cells and they polarization 0 A Membrane Computing Model for Ballistic Depositions 187 Time 0 Time 8 Time 16 Time 24 Time 32 Fig. 4. Example •Ct(env) = {p} • If |Ct(i)|α≥ |Ct(i+ 1)|α then  |Ct(i)|x=|Ct(i)|α− |Ct(i+ 1)|α  |Ct(i)|y= 0 • If |Ct(i)|α<|Ct(i+ 1)|α then  |Ct(i)|y=|Ct(i+ 1)|α− |Ct(i)|α  |Ct(i)|x= 0 Finally, the next theorem claims that the sequence of congurations at times 0,8,16, . . . , 8t, . . . represent the states of an aggregate with a ballistic deposition process. Theorem 1. For all t∈N , C8t is a representative conguration and, if i∈ {1, . . . , L} is the chosen cell for depositing a new particle, then • |C8t+8(i)|α=max{|C8t(i−1)|α,|C8t(i)|α+ 1,|C8t(i+ 1)|α} • For all j∈ {1, . . . , L} , i6=j , |C8t+8(j)|α=|C8t(j)|α Proof. See Appendix 5 Conclusions Understanding how Nature works involves experimental observation and theoretical modeling. This paper is a contribution to the theoretical modeling of a particular case of one of the most interesting process in Physics: the dynamical evolution of the frontier between two dierent media. In this paper, the chosen model has been Ballistic Deposition, but many other deposition processes from Physics, Chemistry and Biology can be also modeled by using similar techniques. On the other hand, Membrane Computing techniques had been used for studying problems from many dierent areas, since Linguistics or Complexity Theory to Computer Graphics or Cancer Modeling 2 , but this is the rst time that P systems are used to model deposition processes. This paper can be extended in several ways. One of them is to extend the study to more dimensions, i.e., to consider the particles as 3D solids falling down 2 See [4] for details. 194 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez The equality (1) holds because C8t is a representative conguration and in this case |C8t(i−1)|α>|C8t(i)|α . The inequality (2) holds because in this case |C8t(i+1)|α≥ |C8t(i−1)|α and nally, the last equality holds by the denition of representative conguration and |C8t(i+ 1)|α>|C8t(i)|α . The rule [ ]i−1,[c2]+ i→[c3]− i−1,[ ]i can also be applied. Therefore, C8t+4(i−1) = {y|C8t(i)|y−|C8t(i−1)|xα|C8t(i−1)|αc3}− C8t+4(i) = {α|C8t(i)|α+|C8t(i)|y} C8t+4(j) = C8t(j) , for all j∈ {1, . . . , i −2, i + 1, . . . , L} and C8t+4(env) = ∅ . As no x are present in cell i−1 , C8t+4(i−1) Ri−1 6 −→ C8t+5(i−1) = {y|C8t(i)|y−|C8t(i−1)|xα|C8t(i−1)|αc4}−Ri−1 7 −→ C8t+6(i−1) = {y|C8t(i)|y−|C8t(i−1)|xα|C8t(i−1)|αc5}−Ri−1 8 −→ C8t+7(i−1) = {y|C8t(i)|y−|C8t(i−1)|xα|C8t(i−1)|αc6}− C8t+k(i) = C8t+4(i) and C8t+k(j) = C8t(j) for all j∈ {1, . . . , i−2, i+1, . . . , L} as no rules aect to them and C8t+k(env) = ∅ for k∈ {5,6,7} . Next, the rule [c6]− i−1→p[ ]i−1 is applied, C8t+8(i−1) = {y|C8t(i)|y−|C8t(i−1)|xα|C8t(i−1)|α} C8t+8(i) = C8t+4(i) and C8t+8(j) = C8t(j) for all j∈ {1, . . . , i−2, i+1, . . . , L} and C8t+8(env) = {p} . Note that |C8t+8(i)|α=|C8t(i)|y+|C8t(i)|α and by hypothesis |C8t(i)|y=|C8t(i+ 1)|α− |C8t(i)|α so |C8t+8(i)|α=|C8t(i+ 1)|α , and that there is no x or y in C8t+8(i) . Finally as in this case |C8t+8(i)|α=|C8t(i+ 1)|α≥ |C8t(i−1)|α=|C8t+8(i−1)|α then |C8t+8(i)|α≥ |C8t+8(i−1)|α and |C8t+8(i−1)|y (1) =|C8t(i)|y− |C8t(i−1)|x= (2) = (|C8t(i+ 1)|α− |C8t(i)|α)−(|C8t(i−1)|α− |C8t(i)|α) = (3) =|C8t(i+ 1)|α− |C8t(i−1)|α= (4) =|C8t(i+ 1)|α− |C8t+8(i)|α The equality (1) holds by the explicit description obtained for |C8t+8(i−1)|y . The equality (2) holds by hypothesis of induction. The third equality by arithmetic and the last by the above reasoning about |C8t+8(i)|α . In order to nish the proof that C8t+8 is a representative conguration we need to see that |C8t+8(i−1)|x= 0 but this holds by the explicit description obtained for C8t+8(i−1) . Case 4: Let us suppose that |C8t(i)|α≥ |C8t(i−1)|α and |C8t(i)|α≥ |C8t(i+ 1)|α In this case |C8t(i)|x=|C8t(i)|α− |C8t(i+ 1)|α≥0 , |C8t(i−1)|x=|C8t(i)|y= 0 and |C8t(i−1)|y=|C8t(i)|α− |C8t(i−1)|α≥0 . A Membrane Computing Model for Ballistic Depositions 195 Also, max{|C8t(i−1)|α,|C8t(i)|α+ 1,|C8t(i+ 1)|α}=|C8t(i)|α+ 1 . We will prove that C8t+8 is a representative conguration, |C8t+8(i)|α=|C8t(i+ 1)|α+ 1 and |C8t+8(j)|α=|C8t(j)|α for j∈ {1, . . . , i −1, i + 1, . . . , L} C8t(i)Ri ∗ −→ C8t+1(i) = C8t(i)∪ {c0}+Ri 1 −→ C8t+2(i) = C8t(i)∪ {c1}+Ri 2 −→ C8t+3(i) = C8t(i)∪ {c2}+ C8t+k(j) = C8t(j) , for all j∈ {1, . . . , i −1, i + 1, . . . , L} as no rules aect to them and C8t+k(env) = ∅ for k∈ {1,2,3} . As cell i has positive electrical charge in C8t+3 , then we apply the rule [ ]i−1,[c2]+ i→[cn3]− i−1,[ ]i obtaining C8t+4(i−1) = C8t(i−1) ∪ {cn3}− C8t+4(j) = C8t(j) for all j∈ {1, . . . , i −2, i, . . . , L} and C8t+4(env) = ∅ After that, C8t+4(i−1) = C8t(i−1) ∪ {cn3}−Ri−1 10 −→ C8t+5(i−1) = C8t(i−1) ∪ {cn4}−Ri−1 11 −→ C8t+6(i−1) = C8t(i−1) ∪ {x y c5}− C8t+k(j) = C8t(j) , for all j∈ {1, . . . , i −2, i, . . . , L} as no rules aect to them and C8t+k(env) = ∅ for k∈ {5,6} . At this step rules [c5→c6]− i−1 and [x]− i−1,[ ] →[ ]i−1[z]i are applied simultaneously and therefore the object x in cell i−1 is sent into cell i transformed into an object z . Hence C8t+7(i−1) = C8t(i−1) ∪ {y c6} C8t+7(i) = C8t(i)∪ {z} C8t+7(j) = C8t(j) , for all j∈ {1, . . . , i −2, i + 1, . . . , L} as no rules aect to them and C8t+7(env) = ∅ . Now, rules [c6]i−1→p[ ]i−1 and [z→x α]i can be applied, then C8t+8(i−1) = C8t(i−1) ∪ {y} C8t+8(i) = C8t(i)∪ {x α} C8t+8(j) = C8t(j) , for all j∈ {1, . . . , i −2, i + 1, . . . , L} as no rules aect to them and C8t+8(env) = {p} . Note that |C8t+8(i)|α=|C8t(i)|α+ 1 and that there is no x in C8t+8(i−1) and no y in C8t+8(i) . Finally, as in this case |C8t+8(i−1)|α=|C8t(i−1)|α<|C8t(i)|α+ 1 = |C8t+8(i)|α and |C8t+8(i+ 1)|α=|C8t(i+ 1)|α<|C8t(i)|α+ 1 = |C8t+8(i)|α , then |C8t+8(i−1)|α<|C8t+8(i)|α and |C8t+8(i+ 1)|α<|C8t+8(i)|α so |C8t+8(i−1)|y (1) =|C8t(i−1)|y+ 1 (2) =|C8t(i)|α− |C8t(i−1)|α+ 1 (3) =|C8t+8(i)|α− |C8t+8(i−1)|α and |C8t+8(i)|x (1) =|C8t(i)|x+ 1 (2) =|C8t(i)|α− |C8t(i+ 1)|α+ 1 (3) =|C8t+8(i)|α− |C8t+8(i+ 1)|α 196 C. Graciani-Díaz, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez The equality (1) holds by the explicit description obtained for C8t+8(i) . The equality (2) holds by hypothesis of induction and the last equality holds by the above reasoning about |C8t+8(i)|α and because for all j∈ {1, . . . , L} , i6=j , |C8t+8(j)|α=|C8t(j)|α , in particular for j=i−1 and j=i+ 1 . Case 5: Let us suppose that |C8t(i+ 1)|α>|C8t(i)|α≥ |C8t(i−1)|α In this case |C8t(i−1)|x=|C8t(i)|x= 0 , |C8t(i−1)|y=|C8t(i)|α−|C8t(i−1)|α≥0 , |C8t(i)|y=|C8t(i+ 1)|α− |C8t(i)|α>0 . Also, max{|C8t(i−1)|α,|C8t(i)|α+ 1,|C8t(i+ 1)|α}=|C8t(i+ 1)|α . We will prove that C8t+8 is a representative conguration, |C8t+8(i)|α=|C8t(i+ 1)|α and |C8t+8(j)|α=|C8t(j)|α for j∈ {1, . . . , i −1, i + 1, . . . , L} As y is present in cell i , C8t(i)Ri ∗ −→ C8t+1(i) = C8t(i)∪ {c0}+Ri 1,Ri 3 −→ C8t+2(i) = {α|C8t(i)|α} ∪ {z|C8t(i)|yα|C8t(i)|yc1}+ C8t+k(j) = C8t(j) , for all j∈ {1, . . . , i −1, i + 1, . . . , L} as no rules aect to them and C8t+k(env) = ∅ for k∈ {1,2} . As cell i has positive electrical charge in C8t+2 , then we apply the rules [ ]i−1,[z]+ i→[y]i−1,[ ]i and [c1→c2]+ i obtaining C8t+3(i−1) = C8t(i−1) ∪ {y|C8t(i)|y} C8t+3(i) = {α|C8t(i)|α+|C8t(i)|yc2} C8t+3(j) = C8t(j) , for all j∈ {1, . . . , i −2, i + 1, . . . , L} and C8t+3(env) = ∅ . Now, the rule [ ]i−1,[c2]+ i→[c3]− i−1,[ ]i can be applied. Therefore, C8t+4(i−1) = C8t(i−1) ∪ {y|C8t(i)|yc3}− C8t+4(i) = {α|C8t(i)|α+|C8t(i)|y} C8t+4(j) = C8t(j) , for all j∈ {1, . . . , i −2, i + 1, . . . , L} and C8t+4(env) = ∅ . After that, C8t+4(i−1) = C8t(i−1) ∪ {y|C8t(i)|yc3}−Ri−1 6 −→ C8t+5(i−1) = C8t(i−1) ∪ {y|C8t(i)|yc4}−Ri−1 7 −→ C8t+6(i−1) = C8t(i−1) ∪ {y|C8t(i)|yc5}−Ri−1 8 −→ C8t+7(i−1) = C8t(i−1) ∪ {y|C8t(i)|yc6}− C8t+k(i) = {α|C8t(i)|α+|C8t(i)|y} and C8t+k(j) = C8t(j) , for all j∈ {1, . . . , i − 2, i + 1, . . . , L} and C8t+k(env) = ∅ for k∈ {5,6,7} . Next, the rule [c6]i−1→p[ ]i−1 is applied, C8t+8(i−1) = C8t(i−1) ∪ {y|C8t(i)|y}− C8t+8(i) = {α|C8t(i)|α+|C8t(i)|y} and C8t+8(j) = C8t(j) , for all j∈ {1, . . . , i − 2, i + 1, . . . , L} and C8t+8(env) = {p} . Note that |C8t+8(i)|α=|C8t(i)|α+|C8t(i)|y and by hypothesis |C8t(i)|y=|C8t(i+ 1)|α− |C8t(i)|α so |C8t+8(i)|α=|C8t(i+ 1)|α=|C8t+8(i+ 1)|α , and that there is no x or y in C8t+8(i) . Finally, as |C8t+8(i−1)|α=|C8t(i−1)|α<|C8t(i)|α+|C8t(i)|y=|C8t+8(i)|α , then |C8t+8(i−1)|α<|C8t(i)|α A Membrane Computing Model for Ballistic Depositions 197 and |C8t+8(i−1)|y (1) =|C8t(i−1)|y+|C8t(i)|y (2) = (|C8t(i)|α− |C8t(i−1)|α)+(|C8t(i+ 1)|α− |C8t(i)|α) (3) =|C8t(i+ 1)|α− |C8t(i−1)|α (4) =|C8t+8(i)|α− |C8t+8(i−1)|α The equality (1) holds by the explicit description obtained for C8t+8(i−1) . The equality (2) holds by hypothesis of induction. The third equality by arithmetic and the last equality holds by the above reasoning about |C8t+8(i)|α and because for all j∈ {1, . . . , L} , i6=j , |C8t+8(j)|α=|C8t(j)|α , in particular for j=i−1 . In order to nish the proof that C8t+8 is a representative conguration we need to see that |C8t+8(i−1)|x= 0 but this holds by the explicit description obtained for C8t+8(i−1) .