An approach to Ballistic deposition based on membrane computing

An Approach to Ballistic Deposition Based on Membrane Computing 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 Ballistic Deposition was proposed by Vold [10] and Sutherland [9] as a model for colloidal aggregation. These early works were later extended to simulate the process of vapour 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 first particle it contacts, which may result in lateral growth. In this paper we present a first P system model for Ballistic Deposition with d= 1. 1 INTRODUCTION Some recent discoveries on the dynamical process of surface growth have encouraged the scientific 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 with the scale of observation and surfaces on Nature are far from be smooth if observed at appropriate scale. The propagation of forest fires [5], the growth of a colony of bacteria [3] or the propagation of reaction fronts in catalysed reactions [1] are real-world examples where the frontier between two media are far from being smooth. In these cases, the interfaces can be hardly modelled with Euclidean geometry 1 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. 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 modelling BD in a discrete approach. The paper is organised as follows: first the Ballistic Deposition model is briefly 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 snowflakes on the ground floor. The randomness in the deposition process leads to a rough surface. There exist many deposition models which try to represent different natural process. The simplest way to define 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?. Ballistic Deposition (BD) was proposed by Vold [10] and Sutherland [9] as a model for colloidal aggregation. These early works were later extended to simulate the process of vapour 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). 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 first 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 [7], where all particles are assumed identical. In Penrose’s mathematical model, the substrate is Rd× {0}, identified with Rdor some subregion thereof. All particles are (d+ 1)-dimensional ?A good starting point for the study of depositions is [2]. 2 A B A0 B0 ? ? Figure 1 Ballistic Deposition solids. Particles arrive sequentially at random positions in Rd. When a particle reaches 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 fixed. The difference 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 0denote the origin in Zd. A displacement function is a mapping D from Zdto [−∞,∞)verifying: •D(0)=1 •The set N={x∈Zd:D(x)6=−∞} is finite but has at least two elements (one of which is the origin) For x∈Zd, let Nx={x+y:y∈ N} and N∗ x={x−y:y∈ N}. The set Nis a neighbourhood of the origin and Nxis a neighbourhood of x. The idea of a displacement function is that if a particle arrives at z∈ Nx then it cannot slide down the ray z×[0,+∞)below the position at height D(z−x). In this way, if h(x, t)measures the height of the interface at site xat time tthen h(x, t+1) = max{h(y, t)+D(x−y) : y∈Zd}. We have 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 [8], the nearest neighbour model, where N={z∈Zd:kzk1≤1}(being kzk1=Pi=d i=1 |zi|for all z= (z1, . . . , zd)∈Zd) and the displacement function Dis given by D(x)=0for x∈N−{0}. We are considering that the 3 dimension of the substrate is d=1 and therefore h(x, t + 1) = max{h(x−1, t), h(x, t)+1, h(x+ 1, t)} 3 P SYSTEMS The chosen P systems model can be considered as 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 represents 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 polarisations of the cells. Both features allow us an efficient 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 with fewer ingredients falls out of the scope of this paper. Formally, a deposition P system of degree Lis a tuple of the form Π = (O, P, µ, env, v1, . . . , vL, venv, R)where: 1. Ois the alphabet of objects; 2. P={0,+,−} is the set of polarisations. Each membrane will be associated with one polarisation. 3. µis a cell structure consisting of Lcells bijectively labelled with {1, . . . , L}. For every i∈ {1, . . . , L−1}there exists an edge between the cell iand the cell i+1. We will also consider an edge between the cell Land the cell 1. For the sake of simplicity, we will identify the indices L+1 and 1; also, if a cell has polarisation 0, we will omit the symbol 0. The initial polarisation of all membranes is 0. 4. env is the environment. It represents the region surrounding the cell structure µ. Some objects can be also placed in this region. 5. v1, . . . , vL, venv are strings over O, describing the multisets of objects placed in the corresponding cells of µand in the environment, respectively. 6. Ris a finite set of rules, of the following forms: 4 (a) [u1→u2]e iwhere i∈ {1, . . . , L},e∈Pand u1, u2∈O∗. These are object evolution rules associated with cells and depending only on the label and the polarisation of the cell. The string u1 has at least one object. (b) a[ ]e1 i→[b]e2 iwhere i∈{1, . . . , L},e1, e2∈Pand a, b∈O. These are send-in rules. An object of the environment is introduced in the membrane ipossibly modified. The polarisation of the cell can also change. (c) [a]e1 i→b[ ]e2 iwhere i∈ {1, . . . , L},e1, e2∈Pand a, b ∈O. These are send-out rules. An object is sent out to the environment possibly modified. The polarisation of the cell ican also change. (d) [a]e1 i[ ]i+1 →[ ]i[b]e2 i+1 and [ ]i[a]e1 i+1 →[b]e2 i[ ]i+1 where i∈ {1, . . . , L},e1, e2∈Pand a, b ∈O. These are communication rules. An object ais sent, possibly modified, to an adjacent cell. Rules are applied according to the following principles: •Rules are used as usual in the framework of membrane computing, that is, in a maximally 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: as usual in P systems with polarisations, only one change of polarisation can affect a membrane, i.e., if two or more rules of types (b), (c) and (d) can be applied to a membrane, then only one of them is applied, non-deterministically chosen. •All the elements which are not involved in any of the operations to be applied remain unchanged. •Several rules can be applied to different objects in the same cell simultaneously. •If rules of type (a) are used in the same time with any of the type (b), (c) or (d), then all these are applied, but we will consider that the object evolution rules (a) are performed before the other ones. This consideration is useful because the rules that send objects across a membrane can also change its polarisation. 5 4 MODELLING BALLISTIC DEPOSITION In this section we will consider a system of Ballistic Deposition with L columns and we will provide a deposition P system which simulates its dynamics. Let us consider the deposition P system 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 i∈ {1, . . . , L}. As remarked before, we will identify the indices L+1 and 1as being the same and similarly for 0 and L; and, if a cell has polarisation 0, we will omit the symbol 0. As usual, λrepresents the empty word. Set (A)– Deposition rules: Ri ∗≡p[ ]i→[c0]+ i In the BD model (see Section 2) , a particle is deposited on the top of a column randomly chosen. We simulate this process by these rules. A particle pin the environment is sent to one of the cells. This particle activates the cell (the polarisation of the cells turns on positive) and goes into the cell as the object c0. Set (B)– Rules for cells with positive polarisation: Ri 1≡[c0→c1]+ iRi 2≡[c1→c2]+ iRi 3≡[y→z α]+ i Ri 4≡[ ]i[c2]+ i+1 →[cn3]− i[ ]i+1 Ri 5≡[ ]i[z]+ i+1 →[y]i[ ]i+1 The object c0in a cell ievolves to c2in two waiting steps before being sent to the cell i−1transformed into cn3. These waiting steps check the occurrence of objects yinside the cell. If any yoccur, each of then evolves to z α at the same time in which c0evolves to c1and in the following step each zis sent to the cell i−1transformed into y(the polarisation of the cell ichanges). If this happens, rule Ri−1 4is not triggered because the cell containing c2has not positive charge. Set (C)– Rules for cells with negative polarisation: Ri 6≡[c3→c4]− iRi 7≡[c4→c5]− iRi 8≡[c5→c6]− i Ri 9≡[c6]− i→p[ ]iRi 10 ≡[cn3→cn4]− iRi 11 ≡[cn4→x y c5]− i Ri 12 ≡[x]− i[ ]i+1 →[ ]i[z]i+1 Set (D)– Rules for cells with polarisation zero: Ri 13 ≡[cn4→c5]iRi 14 ≡[c5→c6]iRi 15 ≡[c6]i→p[ ]i Ri 16 ≡[z→x α]iRi 17 ≡[x y →λ]iRi 18 ≡[ ]i[c2]i+1 →[c3]− i[ ]i+1 The object c2produces the objects c3and c4, or the objects cn3and cn4. In 6 both cases, the objects c5and c6are produced. The object c6sends to the environment an object pwhich will go into a cell in the next step according to the set of rules Ri ∗. As in the set of rule (B), the counter ckgoes on till it reaches c6. The object c6sends to the environment an object pwhich 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 x, y which occur in a cell disappears in the next step. 4.1 Informal description of the computations For a better understanding of the computation, let us remark that the configurations at time 8twith t∈N, represent the state of a BD system after the deposition of the t–th particle. Below we will formalise 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: •prepresents the particle that arrives to the substrate. When it is deposited, it disappears from the environment, then the information encoded in several cells change. When the computation inside the cells finishes, a new particle is sent to the environment and the process starts again. In this way only in the steps 8t, a particle pappears in the environment. •The multiplicity of αin the cell irepresents the height of the column i in the BD model. Finally, the remaining objects inside the cells at time 8tare of types xand y. The objects xor yinside the cell irepresent the difference of height between the cell iand the cell i+1. •The multiplicity of xin the cell irepresents the number of units the column iis higher than column i+1 in the BD model. •The multiplicity of yin the cell irepresents the number of units the column iis lower than column i+1 in the BD model. From the previous description we have that at time 8t, we can find inside a cell either objects x,yor none of them, but we will never find both simultaneously. Table 2 shows an example of evolution of a simple Ballistic Deposition system with four columns where four particles have been deposited sequentially on the columns 3,2,2 and 1. The configurations at times 8twith 7 Time Rules Env. Configuration 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 Figure 2 Table with the first eight steps t∈ {0, . . . , 4}represent the surface of the Ballistic Deposition model after the fall of the t–th particle (Fig. 3). We finish this section by formally showing that this deposition P system of degree Lsimulates the ballistic deposition on a substrate with Lcolumns. In this way we need the definition of a representative configuration. The idea behind the definition is quite intuitive. Along the computation, some of the configurations have no meaning with respect to the deposition process, there are merely auxiliary steps of the computation. Only some of the configurations represent states of the aggregate in the deposition process. Such configurations will be called representative configurations. Note that all rules are applied in a deterministic way but the rule Ri ∗ (i∈ {1, . . . , L}). Depending on the rules Ri ∗chosen we have different computations. Let Cbe an arbitrary computation of the P system and t∈N. We will denote by Ctthe configuration of the P system at time tin such computation. Ct(i)denotes the pair (m, e), where mis the multiset of objects of the cell i at time tin the configuration Ct, and eis the electrical charge of that cell (we 8 TIME 0 TIME 8 TIME 16 TIME 24 TIME 32 Figure 3 Example denote it by {m}e). Finally, |Ct(i)|adenotes the multiplicity of the object a in Ct(i). Definition Let Ctbe a configuration of a deposition P systems of degree L at time t. We will say that Ctis representative if for all i∈{1, . . . , L}, •Only objects α, x and ycan occur inside the cells and all the cells have polarisation 0 •Ct(env)={p} •If |Ct(i)|α≥ |Ct(i+1)|αthen |Ct(i)|x=|Ct(i)|α−|Ct(i+1)|αand |Ct(i)|y=0. •If |Ct(i)|α<|Ct(i+1)|αthen |Ct(i)|y=|Ct(i+1)|α−|Ct(i)|αand |Ct(i)|x=0 Finally, the next theorem claims that the sequence of configurations at times 0,8,16, . . . , 8t, . . . represent the states of an aggregate with a ballistic deposition process. Theorem Let Can arbitrary computation of the P systems. For all t∈N,the configuration C8tis a representative configuration 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, we have |C8t+8(j)|α=|C8t(j)|α Proof See Appendix. 2 5 CONCLUSIONS Understanding how Nature works involves experimental observation and theoretical modelling. This paper is a contribution to the theoretical modelling of 9