Approximating Non-discrete P Systems

Approximating Non-discrete P Systems Andr´es Cord´on-Franco and Fernando Sancho-Caparrini Dpt. Computer Science and Artificial Intelligence, E.T.S.Ingenier´ıa Inform´atica, University of Seville, Spain {acordon, fsancho}@us.es Abstract. The main goal of this paper is to propose some geometric approaches to the computations of non-discrete P systems. The behavior of this kind of P systems is similar to that of classic systems, with the difference that the contents of the membranes are represented by non-discrete multisets (the multiplicities can be non-integers) and, consequently, also the number of applications of a rule in a transition step can be non-integer. 1 Introduction Usual variants of P systems have only a finite number of options in every step of their computations and, in consequence, an associated computation tree is defined for them (see [5] or [6] for a formal definition of these concepts). In this way, irrespectively whether they are non-deterministic or probabilistic P systems [3], we obtain a discrete space (possibly infinite) of computations where the system evolves. Here we will work with a variant which can evolve in every step in a nondiscrete number of possibilities. For that, we will not use discrete multisets, but an extension of them where the multiplicity of the objects can be any positive real number. The inspiration of this variant comes from the fact that, in vitro, we can control neither the application of the rules nor the exact number of objects in every membrane, but we deal with an approximate number of applications. If we allow to work with the concentrations of the objects in the membranes instead of the exact number of objects that are involved in the reactions, then we must deal with a non-integer number of applications of the rules. In this way, the multiplicity of an object will not reflect the exact number of identical copies of it in a membrane, but its concentration in the solution (a similar idea was firstly used in [2] in order to simulate de photosynthesis process by membrane devices). Once we have an idea about what non-integer multiplicity can mean, and we establish non-discrete multisets as a theoretical tool to handle this idea (Section 2), we define and formalize in Section 3 non-discrete P systems. Such systems can contain a non-discrete multiset of objects in every membrane, and evolve by applying a non-integer amount of times every rule (of course, always under the assumption that there are objects enough for such an application). In Section 4 we define the space of extremal transitions as the set of transitions consuming the maximal amount of objects in the usual sense of maximality (we cannot apply more rules simultaneously), and we study some simple geometric properties of them. Section 5 is devoted to the study of some approximating properties on the computations of non-discrete P systems. For that, we define some distances in the set of multisets and transitions, and establish some bounds in the evolution of the system. Finally, the paper closes with some conclusions and possible future work in the environment of non-discrete P systems. 2 Non-discrete Multisets As it was proceeded also in [2], we can define a generalization of multisets by using non integer multiplicities in the following way. Definition 1. Let Vbe a finite alphabet. A non-discrete multiset (ND-multiset) over Vis an application, w:V→IR +. We denote by NDM(V)the set of nondiscrete multisets over V. In a similar way to multisets, we can define the support of an ND-multiset (supp(w)), as well as the usual operations between them: 1. Addition: (w1+w2)(a)=w1(a)+w2(a). 2. Subtraction: (w1−w2)(a)=w1(a)−w2(a) (it is not an inner operation). 3. Arithmetic subtraction: (w1w2)(a) = max{w1(a)−w2(a),0}. 4. External product by real numbers: (n·w)(a)=n·w(a). and the usual relations: 1. w1⊆w2(w1≤w2)⇐⇒ ∀ a∈V(w1(a)≤w2(a)) (provides a partial order in NDM(V)). 2. w1=w2⇐⇒ ∃ a∈V(w1(a)=w2(a)). Finally, 0stands for the empty ND-multiset (∀a∈V(0(a) = 0)). 3 Non-discrete P Systems Now we formalize the variant of P systems that makes use of ND-multisets. In this variant we allow neither the use of dissolutions nor active membranes (creation, duplication, charges, etc.), but we include in it the (now) classic transition P systems (where we can transform and move objects between adjacent membranes) and the communication ones (where we only can move objects taking into account the elements inside and immediately outside of the membrane). In order to do that, we define the ball of a membrane as the set of membranes adjacent with it (and itself). Definition 2. Let µbe a membrane structure (a directed tree). For every node of µ,x, the ball of xin µis the set Bµ(x)={y∈µ|x→y∨y→x∨y=x} (usually, we write B(x)instead of Bµ(x)). In this context, a rule over a membrane structure is a pair of applications, indicating the objects consumed and the objects created, respectively, in every membrane. We say that a rule is associated with a membrane x, if the only membranes affected by the application of the rule are those adjacent to x. Definition 3. A rule over a membrane structure µis an application r:µ→ NDM(V)×NDM(V)(we will denote r=(r1,r 2)). We say that the rule ris associated with x∈µif the following condition holds: ∀y/∈B(x)(r(y)=(0,0)). Example 1. Let us consider the membrane structure µ=[ 1[2]2[3]3]1, the alphabet V= {a, b, c, d}, and the following two rules, r(transition rule) and s(communicating rule), associated with membranes 2 and 3, respectively, written in the usual form: r:ab →c(d, out), s:(ab, in;cd, out). These rules are expressed in our system as: r1(1) = 0,r 1(2) = ab, r1(3) = 0, r2(1) = d, r2(2) = c, r2(3) = 0, and s1(1) = ab, s1(2) = 0,s 1(3) = cd, s2(1) = cd, s2(2) = 0,s 2(3) = ab. (We use here the standard notation for multisets: w∈NDM(V) will be represented by aw(a)bw(b)cw(c)dw(d)). Note 1. This representation of rules is useful not only in order to unify transition and communicating rules, but it also allows the generalization of this kind of rules from tree-like membrane structures to general graphs (or indeed hypergraphs, where the set of hyperedges are not pairs, but general subsets of vertices). For example, in a structure with 3 membranes, we can consider the following rule, r, that is not associated with any membrane, unless we extend the concept of membrane structure to capture more complex graphs: r1(1) = a, r1(2) = b, r1(3) = c, r2(1) = c, r2(2) = a, r2(3) = b. Indeed, if dissolution is not allowed, then the relations between membranes are determined by the rules. We define a non-discrete P system as a membrane structure with a set of rules over it. Definition 4. Anon-discrete P system over an alphabet Vis a pair Π=(µ, R), where µis a membrane structure, and Ris a finite set of rules over µ. Acell is defined by assigning an ND-multiset to every membrane of the structure. Definition 5. Acell for Πis an application C:µ→NDM(V). The set of cells for Πwill be denoted by Cell(Π). Starting from a cell, a transition is a non-discrete application of the rules in a parallel manner. In this way, we can also see the transitions as ND-multisets over the set of rules, where the multiplicity of every rule indicates the number of times that the a rule is applied. Definition 6. Let Π=(µ, R)be a non-discrete P system, and let Cbeacell for Π.Atransition for Cis a non-discrete multiset over R,T∈NDM(R), such that for every x∈µ  r∈R T(r)·r1(x)⊆C(x). We will denote by Tr(C)the set of transitions for C. Now, the formalization of the application of the rules according to one selected transition can be given. Definition 7. Let Πbe a non-discrete P system, Cbe a cell for Π, and T∈ Tr(C). The cell obtained from Cby the application of Tis the cell C=T(C), such that for every x∈µ: C(x)=C(x)+ r∈R T(r)·r2(x)− r∈R T(r)·r1(x). If we give an enumeration {x1,...,x j}of the nodes of µ, and an enumeration {r1,...,rN}of the rules of R, then we can write a transition in the following matricial form: [C 1,...,C j]=[C1,...,C j]+[T1,...,T N]·⎡ ⎢ ⎣ r1 2(x1)−r1 1(x1)... r 1 2(xj)−r1 1(xj) . . ..... . . rN 2(x1)−rN 1(x1)... r N 2(xj)−rN 1(xj) ⎤ ⎥ ⎦, where, Ci,C  i,T istand for C(xi),C (xi),T(rj), respectively. This matrix form can be briefly written as T(C)(x)=C(x)+T·(R2−R1)(x),∀x∈µ, and T(C)=C+T·(R2−R1). 4 Extremal Transitions The set of extremal transitions is the set of transitions consuming the maximal amount of objects, in the following sense. Definition 8. The set of extremal transitions for Cis the set of maximal points of Tr(C)(regarding the partial order defined in NDM(R)), that is, ExTr(C)={T∈Tr(C):|∀T∈Tr(C)(T=T→¬(T≥T))}. In other words, if we apply an extremal transition, then we cannot simultaneously apply further rules over the remaining objects. As a difference with the discrete case, in the non-discrete one we obtain that the set of transitions has good geometrical properties. Proposition 1. Let Πbe a non-discrete P system. For every cell Cfor Πwe obtain that its set of transitions, Tr(C), is a convex and compact set. Proof. Let Cbe a cell for Π. To see that Tr(C) is a convex set, let T,T∈Tr(C)be two transitions for C, and let p∈[0,1]. We prove that p·T+(1−p)·T∈Tr(C). It is direct to check that, for all r∈R,p·T(r)+(1−p)·T(r)∈IR +holds. Let x∈µ. Then,  r∈R (p·T(r)+(1−p)·T(r)) ·r1(x)= =p· r∈R T(r)·r1(x)+(1−p)· r∈R T(r)·r1(x)⊆ ⊆p·C(x)+(1−p)·C(x)=C(x). Finally, it is easy to prove that Tr(C) is compact, because it is a closed and bounded subset of some Euclidean space IRk. The previous result is not true for ExTr(C), that is, it is possible that this set will not be convex. Of course, Extr(C) is a compact set. Example 2. Given the rules r:ab →band s:a2c→bin a membrane, if the content of this membrane in a configuration is a2bc, it is clear that, in the discrete case, we can apply the rules in a maximal parallel manner in two ways: {(1,0),(0,1)}. But, if we allow a non-integer number of applications of the rules, then we obtain the following set of transitions (each of them producing different computations in the evolution of the P system): Ap ={(α1,α 2)|α1+2α2≤2,α 1≤1,α 2≤1,α 1,α 2∈R+}. In Fig. 1 the obtained sets of transitions, Tr, and extremal transitions, ExTr, are represented. aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa Extr Tr Fig. 1. Sets of transitions and extremal transitions 5 Geometric Aspects of Non-discrete P Systems In this section we present some metrics in order to prove that, in case of finite computations (but not only in these ones), we can confine ourselves to the study of non-discrete P systems where the multiplicities and the number of applications are rational numbers. We can consider that all above objects (non-discrete multisets, cells, transitions, sets of transitions, etc.) are subsets or applications in finite-dimensional Euclidean spaces, so all the metrics we define here will be the usual ones. Lemma 1. The following mappings are metrics (in the corresponding spaces): 1. dNDM(V):NDM(V)×NDM(V)−→ IR +, defined by dNDM(V)(w1,w 2) = max{|w1(a)−w2(a)||a∈V}, 2. dC:Cell(C)×Cell(C)−→ IR +, defined by dC(C, C) = max{dNDM(V)(C(x),C(x)) |x∈µ}. We denote by dTr the restriction of dNDM(R)to Tr. By using this metric we can define something like a continuity in the application of the transitions. We can control the evolution of the system by taking near transitions. Lemma 2. Let Πbe a non-discrete P system. There exist N,K > 0(only depending on Π) such that for every cell Cfor Πand T,T∈Tr(C),ifdTr(T,T)< ε, then dC(T(C),T(C)) <KN ε. Proof. We take N=card(R). Because Ris a finite set, there exists K>0 such that: ∀r∈R∀a∈V(r1(x)(a)≤K∧r2(x)(a)≤K). Let x∈µand a∈V;wehave |T(C)(x)(a)−T(C)(x)(a)|=| r∈R (T(r)−T(r)) ·(r2(x)(a)−r1(x)(a))|≤ ≤ r∈R |T(r)−T(r)|·|r2(x)(a)−r1(x)(a)|<KN ε From here we obtain dC(T(C),T(C)) <KN ε. Moreover, we can prove something similar considering two different cells. Lemma 3. Let Πbe a non-discrete P system, C, Cbe two cells for Π, and T,Tbe two transitions for Cand C, respectively. Then dC(T(C),T(C)) ≤dC(C, C)+KN ·dTr(T,T). Proof. Let x∈µ, and a∈V.Wehave |T(C)(x)(a)−T(C)(x)(a)|= =|C(x)(a)+ r∈R T(r)(r2(x)−r1(x))(a)− −C(x)(a)− r∈R T(r)(r2(x)−r1(x))(a)|≤ ≤|C(x)(a)−C(x)(a)|+| r∈R (T(r)−T(r))(r2(x)−r1(x))(a)|≤ ≤|C(x)(a)−C(x)(a)|+ r∈R |T(r)−T(r)|·|(r2(x)−r1(x))(a)|≤ ≤dC(C, C)+KN ·dTr(T,T) We can go further and consider a metric between the sets of transitions. Definition 9. Let Πbe a non-discrete P system, C, Cbe two cells for Π.We define d(Tr(C),Tr(C)) = max{d(T,Tr(C)) |T∈Tr(C)}, where d(T,Tr(C)) = min{dTr(T,T)|T∈Tr(C)}. Proposition 2. In this context, the application Tr is continuous. That is, ∀ε>0∃δ>0(dC(C, C)<δ→d(Tr(C),Tr(C)) <ε). Proof. This result has a very technical proof, whose main idea is to consider the continuous dependence of the transitions on the content of the cells.  The combination of the previous two results allows us to obtain a general approximating procedure in the evolution of a non-discrete P system. Until now, what we can do is to approximate one step (and, of course, a finite computation) of the evolution of a non-discrete P system by another one where the transitions verify the condition of not being “too far” form the original ones, and obtaining a similar final cell (in content). Of course, since the set of transitions are convex, this fact can be used in order to approximate computations by using only rational applications of rules. But, can we do the same if we consider only extremal transitions? The answer to this question is, in general, negative; nevertheless, if we add some (computationally usual) restrictions in our P systems, we can give an affirmative answer. Note 2. If we restrict: –the rules, to be applications r:µ→NDMQ(V)×NDMQ(V), where NDMQ(V) stands for non-discrete multisets where only rational values are considered, –and we start from a rational cell (that is, ∀x∈µ∀a∈V(C(x)(a)∈Q)), then we can make approximations of extremal transitions by means of extremal transitions where all the values are rational. That is, ∀ε>0∀T∈ExTr(C)∃T∈Extr(C)∩QN(dTr(T,T)<ε). Of course, the application of a rational extremal transition over a rational cell provides a rational cell, so we can iterate this procedure along finite computations and obtain an approximation of the computation by means of using only rational numbers. 6 Conclusions This work is intended as an attempt to provide a new variant of P systems where only some approximate behaviors of the real reactions inside the cell are known. This approach is currently used in the development of probabilistic software tools allowing the user to work with concentrations of the reactants, not with the exact number of each of them, trying to be nearer of the real case in laboratory. But, also, this variant can provide new problems related with some other topics. As an example, from the case we have studied here we can observe that the procedure to obtain new cells by the application of the transitions have some similarities with iterated functions, and maybe some results from this topic can be applied here. Moreover, if we consider a probability function associated with the space of transitions, we come into the world of iterated random functions, where a lot of interesting results were obtained in the last years. We can also obtain a new kind of probabilistic non-discrete P systems where the probabilistic measure is defined over a continuous domain. About the relationship between these P systems and the classical ones, one question arises: how can we simulate/approximate the functioning of these devices by means of classical P systems? Of course, of a high interest can be the study of these devices as dynamical systems. Can they have a chaotical behavior (in the sense that two near cells produce very different evolution, not only in content, but in the irrespective orbits of the transitions)? If we model some parts of the cell with these P systems, will we obtain that the life of the cell is in the edge of this chaos? The study of complex systems and their relations with living organizations is now starting, and maybe P systems can provide a new mathematical tool to attack and understand this kind of problems [1]. Acknowledgment The support for this research through the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, is gratefully acknowledged. References 1. A.L. Barab´asi, Z. N. Oltvai. Network biology: Understanding the cell’s functional organization, Nature Review Genetics,5, 2 (2004), 101–13. 2. T.Y. Nishida. Simulations of photosynthesis by a K-Subset transforming system with membranes, Fundamenta Informaticae,49, 1 (2002), 249–259. 3. A. Obtulowicz, Gh. P˘aun. (In search of) Probabilistic P systems, BioSystems,70, 2 (2003), 107–121. 4. Gh. P˘aun. Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 5. Gh. P˘aun. Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 6. M.J. P´erez-Jim´enez, F. Sancho-Caparrini. A formalization of basic P systems, Fundamenta Informaticae,49, 1–3 (2002), 261–272.