Computing Backwards with P Systems

Computing Backwards with P Systems Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected] Summary. Searching all the configurations C′such that produce a given configuration C, or, in other words, computing backwards in Membrane Computing is an extremely hard task. The current approximations are based in heavy hand-made calculus by considering the specific features of the given configuration. In this paper we present a general method for characterizing all the configurations C′such that produce a given configuration Cin transition P systems without cooperation and without dissolution. 1 Introduction Given a computational model with a universal clock, where the time is considered in a discrete way and the transition from a state to the next one is made by a set of rules, it is usual to wonder about the previous state of a given one, or in other words, to wonder about the possibility of computing backwards. Note that the determinism of the model does not make the solution easier, since the determinism of the computation does not lead to the determinism of the reverse computation. One can go deterministically from Sto S0and from S′to S0, but given S0, the reversed computation is not deterministic. A special situation is considered when the rules are reversible. In this case, it suffices to apply the reversed rules to S1according to the computational model to obtain the desired states1. In this paper we study the problem of characterizing the set of configurations of a P systems that produce a given configuration in one computational step. We study the case in which the P system is not necessarily deterministic and the rules are not reversible in general. We will consider a restricted version of transition P systems without cooperation where the membrane structure does not change along the computation. The paper is organized as follows: first we expose an example that shows the necessity of finding a method for computing backwards, avoiding the heavy calculus 1This case is studied for P systems in [1]. 212 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez based on specific features of the given configuration. Next, our P system model is briefly introduced and we present our representation for configurations and rules in such a P system. In Section 6 we prove our main result: The computation of all the configurations C′such that produce a given configuration Ccan be reduced to find solutions of a system of linear equations with values2in N. In Section 7 we provide a general method of calculus based on our theorem. Finally, some conclusions and new open research lines are presented. 2 Motivation The reader is assumed to be familiar with basic elements of membrane computing, e.g., from [4] Let us start with the P system Πwith alphabet Γ={a, b, c}, set of labels H={e, s}, membrane structure µ= [ [ ]e]sand set of rules R Rule 1: [a→b2c]eRule 4: [b→a]s Rule 2: [a]e→a[ ]eRule 5: a[ ]e→[c]e Rule 3: [b→c2]sRule 6: [c→a]e In Section 3, we will give a detailed description of the P system model studied in this paper, but by now it is enough to know that all the rules are applied in a non-deterministic maximal parallel way as usual in the general framework of Membrane Computing. Let us consider now configuration C′= [ [a2b]ea2c]s, i.e., the configuration in which the multiset placed in the membrane labeled by eis a2band the multiset in the membrane sis a2c. Our problem is to find the configuration (or configurations) Csuch that we can go from Cto C′in one computational step. In other words, we want to compute backwards from Cand characterize all the configurations C such that produce C′in one computation step. We can reason in the following way: •We find two objects ain the membrane labeled by ein the configuration C′. Since rules 1 and 2 consume all the objects in the membrane efrom the previous configuration C, we conclude that such pair of objects amust be produced by the application of rule(s) of Π. It is easy to check that only rule 6 produces objects ain membrane e, then the number of objects cin configuration C must be at least 2. If we look at the set of rules again, we observe that object cin membrane eonly triggers rule 6. Hence, if the number of objects cin eis higher than 2 we conclude that the number of objects ain the membrane ein the configuration Cmust be greater than 2. Therefore, we conclude that the number of objects cin the membrane ein configuration Cis equal to 2. •We find one object bin the membrane labeled by ein configuration C′. The unique rule that can produce it is rule 1, but the application of the rule produces at least two objects bin membrane e. Then we conclude that rule 1 is not 2We represent by N={0,1,2, . . . }the set of natural numbers. Computing Backwards with P Systems 213 applied. The occurrence of such object bcan only be explained by considering its occurrence in configuration C. As one can check, no rule is triggered by object bin the membrane e, then the number of objects bin membrane ein the configuration Cequals to 1. •No object care placed in the membrane ein C′. All such objects from the previous configuration Care consumed by rule 6, so no object cin the membrane eimply that rules 1 and 5 have not been triggered. From the previous paragraph, it is known that rule 5 has not been applied. Since all the objects ain membrane ssend objects einto membrane cby means of rule 5 and the numbers of objects cin such membrane in configuration C′is zero, we conclude that in configuration Cno objects aare placed in the membrane s. •We find one object cin the membrane labeled by sin configuration C′. The unique rule that can produce it is rule 3, but the application of the rule produces at least two objects cin membrane s. Then we conclude that rule 3 is not applied. The occurrence of such object bcan only be explained by considering its occurrence in configuration C. As one can check, no rule is triggered by the object cin the membrane s, then the number of objects cin membrane sin the configuration Cequals 1. •Finally, we find two objects ain the membrane labeled by sin the configuration C′. Since rule 5 consumes all the objects in the membrane efrom the previous configuration C, we conclude that such objects amust be produced by the application of rule(s) of Π. Rules 2 and 4 produce objects ain membrane s. Rule 2 is triggered by an object ain the membrane eand rule 4 is triggered by an object bin membrane s. We can also check that all the objects bin sproduce objects a. Nonetheless, an object ain the membrane ecan trigger rules 1 and 2. Fortunately, we have seen that rule 1 is not triggered, so can conclude that all the objects ain membrane etrigger rule 2. We conclude that the number of objects ain membrane ein the configuration Cand the number of objects bin the membrane smust be less than or equal to 2 and the sum of both numbers must be equal to 2. Bearing in mind these considerations, there are three configurations Csuch that produce C′in one computation step: •C1= [ [ bc2]eb2c]s, i.e., we=bc2and ws=b2c. It is easy to check that by applying the rules 4 and 6 we obtain the configuration C′= [ [a2b]ea2c]s. •C2= [ [ abc2]ebc ]s, i.e., we=abc2and ws=bc. In this case, C′is obtained by applying the rules 2, 4 and 6. •C3= [ [ a2bc2]ec]s, i.e., we=a2bc2and ws=c. In this case, C′is obtained by applying the rules 2 and 6. A question arises in a natural way: Could this reasoning be automatic? In other words, given a P system and a configuration C′, is there an algorithm such that outputs the set Cof configurations Cand produce C′in one computational step? We can even go beyond. We wonder if there exists an algorithm such that it takes a P system Πas input and it outputs a mapping RΠwhich, for every 214 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez configuration C′of Π,RΠ(C′) is the set of all computations Csuch that C′is obtained from Cin one computational step. In this paper, we will give a positive answer to both questions. Before, we need to recall the connections between P systems and Linear Algebra. 3 The P System Model Throughout this paper, we will consider a restricted form of transition P systems without dissolution and without output membrane. Considering an output membrane is irrelevant for our study, since we are not interested in the objects placed in a particular membrane, but in the computation process itself. We also restrict the type of rules. Cooperation is not allowed and then rules are triggered by only one object. Namely, along this paper a P system of degree mis a tuple Π= (Γ, H, µ, w1,...,wm, R) where: •Γis an alphabet whose elements are called objects; •His the set of mlabels and mis called the degree of Π. •µis the membrane structure of the P system; membranes are bijectively labelled with the elements of H; •wh1,...,whmare strings that represent multisets over Γassociated with each membrane of µ; •R={R1,...,Rm}is the set of sets of rules, where Riwith i∈ {1,...,m} is a finite set of evolution rules over Γ. The type of evolution rules of Ri depends on the membrane structure µ. Let j1,...,jrbe the labels of membranes immediately inside the membrane i. An evolution rule of Riis of the form a→v, where ais an object from Γand vis an string over Γi tar, where Γi tar = Γ×TARi, for T ARi={here, out} ∪ {injk|k∈ {1,...,r} }. The symbols here,out and injkare called target commands. The rules are applied in a non-deterministic maximally parallel way. Given a rule a→v, the effect of applying this rule in a compartment iis to remove the object aand to insert the objects specified by vin the regions designated by the target commands associated with the objects from v. In particular, •if vcontains (a, here), the object awill be placed in the same region where the rule is applied; •if vcontains (a, out), the object a will be placed in the compartment that surrounds the region where the rule is applied; •if vcontains (a, inj), the object a will be placed in compartment j, provided that jis immediately inside i. Computing Backwards with P Systems 215 In one step, each object in a membrane 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. All the elements which are not involved in any of the rules to be applied remain unchanged. Several rules can be applied to different objects in the same cell simultaneously. Along the computation, the multisets associated with the membranes can change, but the alphabet Γ, the set of labels H, the membrane structure µand the set of rules Rare constant. We will call the 4-uple (Γ, H, µ, R) the skeleton of the P system. Notice that the P system presented in Section 2 is a particular case of this P system model with a slight change of notation in the rules 1. Notation [a→v]hwhere h∈H,a∈Γand vis a string over Γis a short notation to indicate that the rule a→(v1, here)...(vn, here) belongs to the set of rules Rh, with v=v1. . . vn. 2. Notation a[ ]h→[v]hwhere h∈H,a∈Γand vis a string over Γis a short notation to indicate that the rule a→(v1, inh)...(vn, inh) belongs to the set of rules Rh∗, with h∗the label of the membrane surrounding the membrane h and v=v1. . . vn. 3. Notation [a]h→v[ ]hwhere h∈H,a∈Γand vis a string over Γis a short notation to indicate that the rule a→(v1, out)...(vn, out) belongs to the set of rules Rh, with v=v1. . . vn. 4 Changing the Point of View The key idea of the present paper is to consider an algebraic representation for the configurations and the rules of a P system. The starting point is the representation used in [2], but we introduce several changes. First, our elementary objects are pairs of type (a, h)∈Γ×Hmeaning that object a∈Γis placed in the membrane (labeled by) h∈H. Roughly speaking, transitions in P systems are performed by rules in which the occurrence of an element a0in a membrane h0produces the occurrence of β1copies of element a1 in membrane h1,β2copies of element a2in membrane h2, etc. More formally, the rules in the P system model presented above can be reformulated as follows: (a0, h0)→(a1, h1)β1(a2, h2)β2...(an, hn)βn Note that, for all i∈ {1,...,n}, if h0=hithen, (ai, hi) is equivalent to the pair (ai, here). Otherwise, if h06=hiboth membranes must be adjacent (one membrane is the father of the other one). If h0is the father of hi, then the pair (ai, hi) is equivalent to (ai, inhi). Finally, if hiis the father of h0, then the pair (ai, hi) is equivalent to (ai, out). For each i∈ {1,...,n},βirepresents the multiplicity of (ai, hi) in the right-hand side (RHS) of the rule. 216 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez The second basic idea in the representation appears in [3] too. It consists on settling a total order in the set Γ×H. Along the paper, in order to simplify the notation, given an alphabet Γand a set of labels H,dwill denote the cardinal Γ×H. Let us consider a total order Oon the set Γ×H,O:{1, . . . , d} → Γ×H. By using this order, we will represent Γ×Has the finite sequence hγ1,...,γdi, where γiis the i-th pair of Γ×Hin the order O. By using this order, each rule (a0, h0)→(a1, h1)β1(a2, h2)β2...(an, hn)βn can be represented as γ→γα1 1γα2 2. . . γαd d where (a0, h0) = γand for all i∈ {1,...,d}: •If there exists j∈ {1,...,n}such that γi= (aj, hj) then αi=βj. •Otherwise αi= 0. We will say that γ→γα1 1γα2 2. . . γαd dis the pairwise representation of the rule. The use of an order on Γ×Hleads us to a more homogeneous representation of rule γ→γα1 1γα2 2. . . γαd d. It can be represented by a pair hγ,~viwhere γ(the LHS of the rule) belongs to Γ×H, and ~v is a vector of dimension dwhose arguments are in N. Formally, we have the following definition: Definition 1. Let us consider a P system Πwith Γthe alphabet and Hthe set of labels. Let Γ×Hbe the ordered set hγ1,...,γdi. The algebraic representation of the rule γ→γα1 1γα2 2. . . γαd d is the pair (γ,~v)where ~v = (α1,...,αd). We will say that ~v represents the righthand side of the rule ri. Remark 1: Given an order hγ1,...,γdion Γ×H, a pair hγ,~viwhere γ∈Γ×H and ~v is a vector of dimension d(with values in N) defines a unique rule and viceversa, each rule having a unique algebraic representation. Remark 2: If the P system is not deterministic, then there exists at least one γ∈Γ×Hsuch that there exists two different vectors ~v1and ~v2such that pairs hγ,~v1iand hγ, ~v2irepresent two different rules. Let us see an example of this algebraic representation. Example 1. Let us consider the skeleton of the P system considered in Section 2 with Γ={a, b, c},H={e, s},µ= [ [ ]e]sand Rthe set of rules Rule 1: [a→b2c]eRule 4: [b→a]s Rule 2: [a]e→a[ ]eRule 5: a[ ]e→[c]e Rule 3: [b→c2]sRule 6: [c→a]e The set of objects is Γ={a, b, c}and the set of labels is H={e, s}. Let us consider the following total order in Γ×H Computing Backwards with P Systems 217 h(a, e),(b, e),(c, e),(a, s),(b, s),(c, s)i The six rules of the P system can be settled as r1: (a, e)→(b, e)2(c, e)r4:(b, s)→(a, s) r2:(a, e)→(a, s)r5:(a, s)→(c, e) r3:(b, s)→(c, s)2r6:(c, e)→(a, e) By using the previous total order in Γ×H, these rules have the following algebraic representation Rule 1: h(a, e),(0,2,1,0,0,0)iRule 4: h(b, s),(0,0,0,1,0,0)i Rule 2: h(a, e),(0,0,0,1,0,0)iRule 5: h(a, s),(0,0,1,0,0,0)i Rule 3: h(b, s),(0,0,0,0,0,2)iRule 6: h(c, e),(1,0,0,0,0,0)i 4.1 Configurations Aconfiguration of such a P system is the description of the multiset placed in the membranes of the P system in a given instant. Formally, given a P system with working alphabet Γand set of labels H, a configuration Cis a multiset over Γ×H,C:Γ×H→N, and we denote by C(a, m) the multiplicity of object ain the membrane labeled by mof that configuration. The support of C,supp(C), is defined as supp(C) = {(a, m)∈Γ×H|C(a, m)6= 0}and, as usual in multisets theory, Cwill be represented as {(a, m)C(a,m)|(a, m)∈supp(C)}. For example, the configuration of our example [ [ b]ec3]scan be represented as {(b, e),(c, s)3}. From the idea of setting an order on Γ×H, the representation of a configuration via a vector is quite natural. Definition 2. Let us consider a P system Πwith Γthe alphabet, Hthe set of labels and order hγ1, . . . , γdion Γ×H. An algebraic representation of a configuration C:Γ×H→Nis a vector ~ C= (C(γ1),...,C(γd)) that is, the j-th element in ~ Cis a number representing the multiplicity of the j-th element of Γ×H. Let us remark that, if the order on Γ×His set, then there exists a bijective correspondence between a configuration Cand its algebraic representation ~ C. Example 2. As we saw before, the initial configuration [ [ b]ec3]scan be expressed as the multiset C={(b, e),(c, s)3}. If we consider order h(a, e),(b, e),(c, e),(a, s),(b, s),(c, s)i then the algebraic representation of the configuration is ~ C= (0,1,0,0,0,3). 218 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez In order to formalize the concept of computation with this new representation, we will fix some notations. We denote by RHSrthe right-hand side of rule rand for all σ∈Γ×H,|RHSr(σ)|denotes the multiplicity of σin the multiset RHSr. Example 3. Let us consider the pairwise representation of the rule r1: (a, e)→ (b, e)2(c, e), then RHSr1= (b, e)2(c, 2) and |RHSr1|(b, e) = 2. Definition 3. Let us consider an alphabet Γ, a set of labels Hand the set of rules Rof a P system. We will denote by LHS(R)the set of all the pairs from Γ×H that are the left-hand side of a rule from R. Formally LHS(R) = {γ∈Γ×H| ∃r∈R(γ=LHS(r))} Example 4. Let us consider Γ={a, b, c},H={e, s}and Rthe set of rules r1: (a, e)→(c, e)2r2:(a, e)→(a, s)r3:(b, e)→(c, e) r4: (a, s)→(b, s)r5:(a, s)→(b, s)(c, s)2 In this case LHS(R) = {(a, e),(b, e),(a, s)}. Definition 4. Let us consider an alphabet Γand a set of labels Hof a P system Πand let R=hr1,...,rpibe an enumeration of its set of rules with rj= (LHS(rj), ~vj). Let C:Γ×H→Nbe a configuration of Π. Apartition of Cwith respect to Ris a p-uple P=h(r1, k1),...,(rp, kp)i such that for all j∈ {1,...,p},kj≥0and for all γ∈ LHS(R) X LHS(rj)=γ kj=C(γ) Example 5. Let us consider an alphabet Γ={a, b, c}a set of labels H={e, s}, µ= [ [ ]e]sand Rthe set of rules from the example 4 r1: (a, e)→(c, e)2r2:(a, e)→(a, s)r3:(b, e)→(c, e) r4: (a, s)→(b, s)r5:(a, s)→(b, s)(c, s)2 Let us consider a configuration with algebraic representation ~ C= h3,0,1,7,4,1iassociated with order h(a, e),(b, e),(c, e),(a, s),(b, s),(c, s)iof Γ×H. In this case, one possible partition of Cwith respect to Ris P=h(r1,2),(r2,1),(r3,0),(r4,2),(r5,5)i the number associated to each rule is a natural number and LHS(R) = {(a, e),(b, e),(a, s)}, so in order to check that Pis a partition it suffices to check PLHS(rj)=(a,e)kj=k1+k2= 2 + 1 = 3 = C(a, e) PLHS(rj)=(b,e)kj=k3= 0 = C(b, e) PLHS(rj)=(a,s)kj=k4+k5= 2 + 5 = 7 = C(a, s) Computing Backwards with P Systems 219 The different possible partitions capture the idea of different choice of rules in the case of non-deterministic P system. Notice that in the case of a deterministic P system, there exists only one partition P=h(r1, C(LHS(r1))),(r2, C(LHS(r2))),...,(rp, C(LHS(rp)))i In order to obtain a new configuration C′from a given configuration Cand from the set of rules {r1,...,rp}, we need to describe the multiplicity of any σ∈Γ×H in C′. For the calculus of such multiplicity we need •A partition P=h(r1, k1),...,(rp, kp)iof Cwith respect to R. •The set LHS(R) In such multiplicity, each rule ri:γi→RHSriadds the multiplicity of σin the right hand side of the rule multiplied by the value kiin the partition P. If the object is not consumed by any rule, we also add the multiplicity in the original configuration. Formally, for every σ∈Γ×Hwe have: C′(σ) = ½Pi=p i=1 ki· |RHSri(σ)|if σ∈ LHS(R) Pi=p i=1 ki· |RHSri(σ)|+C(σ) if σ6∈ LHS(R) Example 6. Let us come back again to our P system Πwith alphabet Γ={a, b, c}, set of labels H={e, s}, membrane structure µ= [ [ ]e]sand the set of rules R Rule 1: [a→b2c]eRule 4: [b→a]s Rule 2: [a]e→a[ ]eRule 5: a[ ]e→[c]e Rule 3: [b→c2]sRule 6: [c→a]e Let us consider configuration C1= [ [ bc2]eb2c]s, i.e., we=bc2and ws=b2c. It is easy to check that by applying rules 4 and 6 we obtain configuration C′= [ [a2b]ea2c]s. Such configuration can also be obtained by considering the multiplicity of each pair in Γ×Hand using the previous formula. First we consider the partition P=h(r1,0),(r2,0),(r3,0),(r4,2),(r5,0),(r6,2)iand LHS(R) = {(a, e),(b, s),(a, s),(c, e)}. Then, for example, C′(a, s) = k1·0 + k2·1 + k3·0 + k4·1 + k5·0 + k6·0 = 2 ·1 = 2 C′(b, e) = k1·2 + k2·0 + k3·0 + k4·0 + k5·0 + k6·0 + C(b, e) = 0 ·2 + 1 = 1 the remaining multiplicities in configuration C′can be obtained in a similar way. 5 Matrix Associated with the Skeleton After defining the algebraic representation of rules and configurations, we will define a numerical matrix associated with the skeleton of a P system. The next definition of extended set of rules will be used in the definition of the matrix. 226 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez In this way, we hope that this method can be useful for researchers interested in computing backwards in Membrane Computing, since it can consider the problem of finding the previous configurations as a problem of Integer Programming. Finally, this work can be extended in several ways. Not only by going deeper in the concept of computing backwards along a computation (and not only in one step) but exploring if these ideas can be extended to other P system models. Acknowledgment The authors acknowledge the support of the project TIN2006-13425 of the Ministerio de Educaci´on y Ciencia of Spain, cofinanced by FEDER funds, and the support of the Project of Excellence with Investigador de Reconocida Val´ıa of the Junta de Andaluc´ıa, grant P08-TIC-04200. References 1. O. Agrigoroaiei, G. Ciobanu: Dual P Systems. Proceedings of Ninth Workshop on Membrane Computing (P. Frisco, D. Corne, Gh. P˘aun, eds.), Technical report HWMACS-TR-0061, School of Mathematical and Computer Sciences, Heriot-Watt University, Edinburgh, UK, July 2008, 45–58. 2. A. Cord´on-Franco, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Exploring Computation Trees Associated with P Systems. In Membrane Computing, LNCS 3365, Springer, 2005, 278–286. 3. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez: Efficient Computation in Rational- Valued P Systems. Submitted, 2009. 4. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002.