Further Remarks on Trace Languages in P Systems with Symport/Antiport

Further Remarks on Trace Languages in P Systems with Symport/Antiport Guangwu Liu1,2, Mihai Ionescu1 1Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial Tarraco 1, 43005 Tarragona, Spain [email protected], [email protected] 2Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, P.R.China Summary. P systems are parallel molecular computing models which process multisets of objects in cell-like membrane structures. In this paper we consider the trace languages of a special symbol, the traveler, in symport/antiport P systems where, instead of multisets of objects, sets of objects were considered. Two different ways to define the trace language are proposed. One of the families of languages obtained in this way is proved to be equal to the family of regular languages and the other one to be strictly smaller. Some ideas for further research are also considered. 1 Introduction This paper is a contribution to the study of P systems where the trace of an object (traveler), as introduced in [7] and further investigated in [6, 5], is considered. The model belongs to the area of P systems with purely communicative functioning, as introduced in [8], inspired from the biological processes of symport and antiport – see [1], [4] for biochemical details about these kinds of trans-membrane transfer of chemicals (in short, symport is the process in which two molecules pass together, in the same direction through a membrane, while antiport refers to the process when two molecules pass simultaneously through a membrane, but in opposite directions). As explained in [7], we are not interested now in the number of certain objects present in a certain membrane, or in the environment of the system (as in the classical definition of P systems), but in the itineraries of a unique object, the traveler, through the membranes of the system, and in the result (a string of labels of the visited membranes) produced by these itineraries. In this paper, we investigate the power of the family of languages generated by such systems considering sets of objects instead of multisets of objects (as in the classical variants of P systems). 162 G. Liu, M. Ionescu We recall the reader that P systems are distributed parallel computing models which abstract from the structure and the functioning of the living cells. In short, we have a membrane structure, consisting of several membranes enclosed within the skin membrane, and delimiting regions (see Figure 1) where multisets of objects (which evolve according to given evolution rules) are placed. The rules are applied nondeterministically, in a maximally parallel manner. In this way we obtain transitions from a configuration of the system to the next one. A sequence of transitions constitutes a computation; to each halting computation we associate a result, the number of objects from a specified output membrane. For more details on various variants of P systems we refer to [10] and to the papers available at the web address http://psystems.disco.unimib.it/. ' & $ % ' & $ %  Á ¿ À  Á ¿ À ¶ µ³ ´ º ¹· ¸ # "à ! ¶ µ³ ´ ¶ µ³ ´    À @@ @R ¡ ¡ ¡ ¡ª membrane A AU skin elementary membrane membrane region © ©* HHHHHHH Hj @@@ @R Figure 1: A membrane structure 12 3 4 5 6 7 8 9 The P systems models which we consider in this paper are inspired by the real life phenomenon of trans-membrane transport in pairs of chemicals. When two chemicals can pass together through a membrane in the same direction, the process is called symport. When the two chemicals pass only with the help of each other, but in opposite directions, one says that we have antiport. Technically, the formalization in P systems of these biological processes is made through the following rules: (x, in) and (x, out) model the symport, and (x, out;y, in) models the antiport (x, y are strings of symbols representing multisets of chemicals). Of course, this is a generalization of what happens in biology, where mainly pairs of chemicals are coupled. Several classes of P systems of this type were considered. Because such systems work with multisets of objects, it is natural that the result of a computation is a number (or a vector of numbers), de- Further Remarks on Trace Languages in P Systems with Symport/Antiport 163 scribing the multiset of objects present at the end of a computation in a specified output membrane. In the present paper we use another idea: we take into consideration the string of labels of membranes visited by a specified object during a computation, this time not working with multisets of objects but with sets of objects. In this way, a P system will generate a language. In Section 4 we prove that the family of languages generated by P systems with traces, with the traveler marking only once the visited membrane (when entering it) and symport/antiport rules equals REG, the family of regular languages. The variant of P systems (with symport/antiport rules) in which the traveler marks twice the visited membrane (once for entering the membrane and once for getting out of it) generates a family of languages strictly included in REG. 2 P Systems with Symport/Antiport The language theory notions we use here are standard, and can be found, for instance, in [11], [12]. We only mention that we denote by V∗the free monoid generated by an alphabet V;λis the empty string, |x|is the length of x∈V∗, and |x|ais the number of occurrences of the symbol a∈Vin the string x∈V∗. For x∈V∗we denote alph(x) = {a∈V| |x|a≥1}(the set of symbols appearing in x), and for a language L⊆V∗we write alph(L) = Sx∈Lalph(x).By REG we denote the family of regular languages. A membrane structure is pictorially represented by an Euler-Venn diagram (like the one in Figure 1); it can be mathematically represented by a tree or by a string of matching parentheses associated in a standard manner with a tree. A multiset over a set Xis a mapping M:X−→ N. Here we always use multisets over finite sets X(that is, Xwill be an alphabet). A multiset with a finite support can be represented by a string over X; the number of occurrences of a symbol a∈Xin a string x∈X∗represents the multiplicity of ain the multiset represented by x. Clearly, all permutations of a string represent the same multiset, and the empty multiset is represented by the empty string, λ. We first introduce the standard P systems with symport/antiport rules, with multisets of objects, computing sets of numbers. Such a device is a construct Π= (V, µ, w1, . . . , wm, E, R1, . . . , Rm, io), where: 1. Vis the alphabet of chemicals (we call them objects); 2. µis a membrane structure with mmembranes (injectively labeled by positive integers 1,2, . . . , m); m≥1 is called the degree of the system; 3. w1, . . . , wmare strings over Vrepresenting the multisets of objects initially present in the regions of the system, and Eis the set of objects which are supposed to be continuously present outside the system, in the environment, in an arbitrary number of copies; 164 G. Liu, M. Ionescu 4. R1, . . . , Rmare finite sets of rules of the forms (x, in),(x, out), and (x, out;y, in), for x, y ∈V∗; 5. io∈ {1, . . . , m}is an elementary membrane of µ(the output membrane). The rules from a set Riare used with respect to membrane ias suggested above. In the case of (x, in), the multiset of objects xenters the region defined by the membrane, from the immediately upper region; this is the environment when the rule is associated with the skin membrane. In the case of (x, out), the objects specified by xare sent out of membrane i, into the region immediately outside; this is the environment in the case of the skin membrane. The use of a rule (x, out;y, in) means expelling from membrane ithe objects specified by xat the same time with bringing in membrane ithe objects specified by y. The objects from Eare supposed to appear in arbitrarily many copies in the environment (because we only move objects from a membrane to another membrane, hence we do not create new objects in the system, we need a supply of objects in order to compute with arbitrarily large multisets). The rules are used in the nondeterministic maximally parallel manner specific to P systems with symbol-objects. In this way, we obtain transitions between the configurations of the system. A configuration is described by the m-tuple of the multisets of objects present in the mregions of the system, as well as the multiset of objects which were sent out of the system during the computation, others than the objects appearing in the set E; it is important to keep track of such objects because they appear in a finite number of copies in the initial configuration and can enter again the system. We do not need to take care of the objects from Ewhich leave the system because they appear in arbitrarily many copies in the environment (the environment is supposed inexhaustible, irrespective how many copies of an object from Eare introduced into the system, still arbitrarily many remain in the environment). The initial configuration is (w1, . . . , wm, λ).Therefore, a transition means a redistribution of objects among regions (and environment), which is maximal for the chosen set of rules. A sequence of transitions between configurations of the system constitutes a computation; a computation is successful if it halts, i.e., it reaches a configuration where no rule can be applied to any of the objects. The result of a successful computation is the number of objects present within the membrane with the label ioin the halting configuration. A computation which never halts yields no result. The set of all numbers computed by Πis denoted by N(Π). The family of all sets N(Π), computed as above by systems Πof degree at most m≥1, using symport rules (x, in) or (x, out) with |x| ≤ p(we say that |x| is the weight of the symport rule (x, in),(x, out)), and antiport rules (x, out;y, in) with |x|,|y| ≤ q(we say that max(|x|,|y|) is the weight of the antiport rule (x, out;y, in)), is denoted by NOPm(symp, antiq), for m≥1 and p, q ≥0. When the number of membranes is not bounded we replace the subscript mby ∗, and when the weight of rules is not bounded we replace the subscripts pand qby ∗. We use NRE to denote the family of recursively enumerable sets of natural numbers (that is, the family of the length sets of recursively enumerable languages). Further Remarks on Trace Languages in P Systems with Symport/Antiport 165 The following results are the best known in this moment (see [5], [3]): NRE =NOP3(sym2) = NOP3(sym1, anti1) = NOP1(anti2). 3 Considering the Trace of Certain Objects In [7], P systems of the following form were considered: Π= (V, t, T, h, µ, w1, . . . , wm, E, R1, . . . , Rm), where all components V, µ, w1, . . . , wm, E, R1, . . . , Rmare as above, t∈V(a distinguished object, “the traveler”), Tis an alphabet, and h:{1,2, . . . , m} −→ T∪{λ} is a weak coding. The traveler is present in exactly one copy in the system, that is, |w1. . . wm|t= 1 and t /∈E. Let σ=C1C2. . . Ck, k ≥1, be a halting computation with respect to Π, with C1= (w1, . . . , wm, λ) the initial configuration, and Ci= (z(i) 1, . . . , z(i) m, z(i) e) the configuration at step i, 1≤i≤k. If |z(i) j|t= 1 for some 1 ≤j≤m, then we write Ci(t) = j(therefore, Ci(t) is the label of the membrane where tis placed). If |z(i) j|t= 0 for all j= 1,2, . . . , m, then we put Ci(t) = λ. Then, the trace of tin the computation σis trace(t, σ) = C1(t)C2(t). . . Ck(t). The computation σis said to generate the string h(trace(t, σ)), hence the language generated by Πis L(Π) = {h(trace(t, σ)) |σis a halting computation in Π}. We denote by LTPm(symp, antiq) the family of trace languages L(Π) generated by P systems with at most mmembranes and using symport rules of weight at most pand antiport rules of weight at most q. When one of the parameters m, p, q is not bounded, we replace the respective subscript with ∗. The power of these systems was investigated in [7, 6] and the currently best result (stated in [5]) is the following: RE =LTP∗(sym0, anti2). In [5] the following results are also proved: lRE =lLTPl+1(sym0, anti2), lRE =lLTPl+1(sym3, anti0), lRE =lLTPl+2(sym2, anti0), where the parameter lin front of language families indicates that only languages Lwith card(alph(L)) ≤lare considered. 166 G. Liu, M. Ionescu 4 Trace Languages in Symport/Antiport P Systems with Sets of Objects In this section, we consider P systems whose regions contain finite sets of objects, not multisets as in the classical variant of P systems (such systems were investigated in [2] as number generating devices); moreover, we assume that the environment is empty. Such a system is a construction Π= (V, t, µ, w1, . . . , wm, R1, . . . , Rm), where: 1. Vis the alphabet of chemicals (objects); 2. t∈Vis the traveler. There is exactly one traveler tin the system, that is, |w1· · · wm|t= 1; 3. µis a membrane structure with mmembranes (injectively labeled by positive integers 1,2, . . . , m); 4. wiare strings representing the sets of objects present in the regions of µ, 1≤ i≤m; 5. Riis the set of symport and antiport rules associated with the membrane i; they have the forms (x, in),(x, out) and (x, out;y, in), for x, y ∈V∗,1≤i≤ m. The trace of the traveler across membranes is encoded as a string over the alphabet {a1, a2, . . . , am}, by recording, in order, every membrane visited by t. We consider two different cases of marking the trace. In the first one, we count only the event of the traveler entering a membrane, and in this case we denote by LT Pset m(symp, antiq, in) the family of languages generated by P systems with traces and symport/antiport rules over finite set of objects, using at most mmembranes, symport rules of weight at most pand antiport rules of weight at most q. In the second case we take into account both the fact that the traveler enters a membrane and that it exits it (so we collect twice the label of the membrane tvisits). We denote by LT Pset m(symp, antiq, in/out) the family of languages generated in this case, with the usual meaning of the parameters m, p, q. In what follows we investigate the place of these families with respect to Chomsky hierarchy. Theorem 1. LTPset ∗(sym∗, anti∗, in) = REG. Proof. Given a P system Π= (V, t, µ, w1, . . . , wm, R1, . . . , Rm) we can construct a regular grammar G= (C, T, C0, R), where Cis the set of all configurations which can be reached by Πstarting from the initial configuration (this set is finite, because the system only handles a finite number of objects), C0is the initial configuration, and T={a1, a2, . . . , am}. The rules of the grammar are constructed as follows. Further Remarks on Trace Languages in P Systems with Symport/Antiport 167 1. Ci→Cjif Ci→Cjis a transition and the traveler does not enter any membrane; 2. Ci→akCjif Ci→Cjis a transition and the traveler enters membrane k(1 ≤k≤m); 3. Ci→λif Ciis a halting configuration. It is obvious that trace(Π) = L(G) which implies LTPset ∗(sym∗, anti∗, in)⊆ REG. Conversely, given a regular grammar G= (N, T, S, R) (Nis the set of nonterminals, T={a1, a2, . . . , am},S∈N, and Ris the set of productions of the form A→aiB, and A→ai, with A, B ∈N, ai∈T), we can construct a P system as follows. The initial configuration (in the bracketed form) is [cSt[dNN0]0[f1]1[f2]2. . . [fm]m]s,{s, 0,1,2, . . . , m}is the set of labels for membranes, sis the label of the skin membrane, fi(1 ≤i≤m) is the symbol within membrane i,dNN0is the (strings which describes the) set of objects in membrane 0 (Nis the nonterminal alphabet of grammar G,N0is the set of primed versions of elements of N, and d∈V), cSt is the set of objects in the skin membrane, where tis the traveler, Sis the initial symbol of grammar G, and c∈V. In order to simulate a rule A→aiB∈Rwe will use the following rules: step R0Ri 1 (fi, out;cAt, in) 2 (d, out;fi, in) (At, out) 3 (fiB0, out;A, in) (c, out;d, in) 4 (d, out;fi, in) 5 (B, out;dB0, in) where R0and Riare the sets of rules associated with membranes labeled 0 and i, respectively. For the other membranes no rules are specified. The process of simulating a rule A→aiBis detailed below. In the first step, the antiport rule (fi, out;cAt, in) makes the traveler t(altogether with objects cand A) enter membrane labeled i, thus introducing the symbol aiin the trace. In the same time, symbol fi, initially present in membrane i, is expelled within the skin membrane. What is left to simulate is the process of transforming Ato Band to bring the system back to its starting configuration, in order to be ready for a new simulation of a rule. In the second step of computation, rules (d, out;fi, in), and (At, out) indicate that our traveler goes out membrane i(altogether with object A), while fienters membrane labeled 0, with the help of object d(its counterpart in the antiport rule). In the next step, the position of Aand B0in the system is interchanged, in the same time with expelling from membrane labeled 0 the symbol fi. The position of objects c, and dis also modified by the antiport rule that applies for the membrane labeled i. In this moment, our system has the following configuration: 168 G. Liu, M. Ionescu [ficB0t[N{N0−B0}]0[f1]1[f2]2...[d]i. . . [fm]m]s. We have now succeeded in rewriting Ato B0(which is a copy of B). The following thing to accomplish is to make the system gain its initial configuration, this time with Bin the place of Aso the derivation could continue. In step 4, we use rule (d, out;fi, in) to move back fiin its initial place. In the last step of the computation, rule (B, out;dB0, in) sends dand B0in membrane labeled 0 while Bis expelled from membrane labeled 0 to the skin membrane, and the system can now continue to simulate the derivation process. We can continue the above process to simulate nonterminal rules of G. A rule D→aiis simulated using the rule (fi, out;cDt, in)∈Ri. The work of this rule is obvious. The derivation grammar Gends by using such a rule, hence also our system will halt. Clearly, trace(Π) = L(G), hence we also have the inclusion REG ⊆ LTPset ∗(sym∗, anti∗, in). ut If we consider the degree of the P system and the weight of the rules, we can write the previous result in the form mREG =LTPset m+2(sym2, anti3, in). We consider now the in-out case. Theorem 2. LTP set ∗(sym∗, anti∗, in/out)(REG. Proof. We can use the same idea as in the previous theorem to prove the inclusion LTPset ∗(sym∗, anti∗, in/out)⊆REG. The properness of the inclusion is proved by the following counterexample. Consider the language L={a2a3, a2a2a3}and assume that there is a P system Πsuch that trace(Π) = L. Besides the skin membrane, this system must contain at least two membranes, with labels 2 and 3. These membranes can have one of the three relationships indicated in the next figure. ' & $ % ' & $ % ' & $ % ¾ ½ » ¼ ¾ ½ » ¼ ' & $ % # " à ! ' & $ % # " à ! s 2 3 s 2 3 s 3 2 (a) (b) (c) Further Remarks on Trace Languages in P Systems with Symport/Antiport 169 In case (a), in order to generate the string a2a2a3we must have the traveler outside membrane 2, and then a2a3cannot be generated. In case (b), in order to generate the string a2a2a3we must have the traveler in the region between membrane 2 and membrane 3, and then again a2a3cannot be generated. Similarly, in case (c), in order to generate the string a2a2a3we must have the traveler in the region between membrane 3 and membrane 2, and then a2a3cannot be generated. Thus, the equality trace(Π) = Lis not possible, this language is not in LTPset ∗(sym∗, anti∗, in/out). ut 5 Decreasing the Number of Membranes By the definition, in order to obtain a language over an alphabet with msymbols, we have to use a system with at least mmembranes, hence the hierarchy on the number of membranes is trivially infinite in the case of trace languages. This direct dependence of the number of membranes on the number of symbols raises the question whether it is possible to keep bounded the number of membranes even when generating languages over arbitrary alphabets, or at least to use a number of membranes smaller than the number of symbols. We present here three possible ways to address this question. The first proposal is to consider several travelers. For instance, let us suppose that we have T={t1, t2, . . . , tk}a set of ktravelers and that the membrane structure of our P system contains mmembranes. In this case, the alphabet of trace symbols, contains k·msymbols ai,j , where 1 ≤i≤k, and 1 ≤j≤m. Let σ=C1C2. . . Ck, k ≥1, be a halting computation and let Ci(T) = {aij |ti is in membrane j}. We consider trace(T, σ) = {w1w2. . . wk|wi∈V∗, ΨV(wi) = ΨV(Ci(T))}, i.e., we concatenate permutations of strings representing each Ci(T). Then, the trace language defined by a P system with several travelers is LT(Π) = {h(trace(T, σ)) |σis a halting computation in Π}. Thus, LT(Π) is a language over an alphabet with k·msymbols, although we only use mmembranes. Let us consider an example – returning again to the case of P systems with multisets of objects. We take the P system Π= (V, T, µ, w1, w2, w3,{d}, R1, R2, R3), with: 1. V={d, t1, t2}the set of all objects in the system; object dis present in arbitrarily many copies in the environment; 2. T={t1, t2}is the set of travelers; 3. µ= [ [ ]2[ ]3]1is a membrane structure with 3 membranes; 4. w1=t1t2,w2=w3=∅are the sets of objects in the initial configuration; 5. Riis the set of symport rules associated with the membrane i, as follows: