Minimal Cooperation in Symport/Antiport P Systems with One Membrane

Minimal Cooperation in Symport/Antiport P Systems with One Membrane Artiom Alhazov1,2, Yurii Rogozhin2 1Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T`arraco 1, 43005 Tarragona, Spain E-mail: [email protected] 2Institute of Mathematics and Computer Science Academy of Science of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova E-mail: {artiom, rogozhin}@math.md Summary. In this paper we consider symport/antiport P systems with one membrane and rules having at most two objects. Although it has been proved that only finite number sets can be generated by both OP1(sym2) (one-membrane systems with symport rules of weight at most 2) and OP1(sym1, anti1) (one-membrane systems with symport/antiport rules of weight 1), the exact characterization is still an open question. We give some lower bounds, consider a few extensions, and state some open questions. 1 Introduction Membrane systems (also called P systems) with symbol-objects are biologically motivated models of parallel distributed multiset processing – see details in [6]. Distributivity means that the objects (elements of a finite set) are placed in the compartments of the system, defined by a tree-like membrane structure. In symport/antiport P systems [5] – from now on we call them communicative P systems – the objects simply move across the membrane, alone or in groups, in the same direction (symport) or in the opposite directions (antiport). This feature is so powerful, that some restricted classes of these systems are already computationally complete. Each object carries a finite amount of information. It is impossible to perform any nontrivial computation without interaction of different objects. This note is devoted to the study of the “weakest” communicative membrane systems: having at most one membrane and rules of transport of at most two objects. 30 A. Alhazov, Yu. Rogozhin 2 Definitions From now on by a number we mean a nonnegative integer. Let NF IN represent the family of all finite number sets. We will denote by NRE the family of all recursively enumerable number sets, and by NkRE,k≥1, the family of all recursively enumerable sets of numbers greater then or equal to k. A communicative P system with mmembranes is defined as a tuple Π= (O, E, µ, w1,· · · , wm, R1,· · · , Rm, i0), where Ois a finite set of objects (an alphabet), E⊆Ois a subset of objects present in the environment in unbounded quantities, µis a hierarchical structure of mmembranes, delimiting the regions, i0is the label of the output membrane, wiis the initial multiset of objects in region i, 1 ≤i≤m,Riis the set of rules associated to membrane i, 1 ≤i≤m. The multisets are typically represented by strings with a corresponding multiplicity of each object. The rules can be of the following forms: (x, in) and (y, out) are symport rules, and (y, out;x, in) are antiport rules, x, y ∈O+. Application of one of such rules (associated to some membrane i) consists of moving objects through membrane i: a multiset defined by xis moved from region i(contained in membrane i) into the immediately outer region and/or a multiset defined by yis moved from the region containing membrane iinto the region i. The weight of a rule is the maximal number of objects moved in any direction (|x|,|y|in the case of symport rules, and max{|x|,|y|} in the case of antiport rules). The rules are applied in a maximally parallel manner, non-deterministically. A configuration is called halting if no rules are applicable; a sequence of transitions among configurations is called a computation. The result of a halting computation is the number of objects present in the output membrane when the system halts. Collecting the results of all computations of Π, one obtains a number set generated by Π, denoted by N(Π). By NOPm(symi, antij) we will denote the class of all number sets generated by P systems with at most mmembranes, having symport rules of weight at most iand antiport rules of weight at most j. 3 Existing Universality Results The results proved in [4]: NOP1(sym3)⊇N13RE and NOP1(sym1, anti2)⊇ N1RE (the latter result does not use rules exchanging 2 objects for 2 objects) show that the power of cooperation of 3 objects is enough for universality of P systems with one membrane. From now on, we will only consider the rules moving at most 2 objects. It was proved in [2] that NOP3(sym2) = NOP3(sym1, anti1) = NRE, so the power of cooperation of 2 objects is sufficient for the computational completeness of P systems with 3 membranes. The results in [3], that DNaOtP2(sym2) = Minimal Cooperation in Symport/Antiport P Systems with One Membrane 31 DNaOtP2(sym1, anti1) = NRE show that 2 membranes are enough for the tissue case (even for the deterministic computational completeness). Finally, it has been shown in [1] that NOP2(sym2)T=NOP2(sym1, anti1)T=NRE : 2 membranes are enough to generate any recursively enumerable number set modulo the terminal alphabet (i.e., ignoring some objects in the output region). 4 Upper Bound Mainly for these reasons we are especially interested in the following classes: NOP1(sym1, anti1), NOP1(sym2), NOP1(sym2, anti1). It has been shown in [3] that NOP1(sym1, anti1)⊆NF IN. It has been shown in [4] that NOP1(sym2)⊆N F IN. The idea behind the proofs is that if a P system has a mechanism of continuously increasing the number of objects in region 1, then it cannot halt. These results are totally opposite to the completeness ones. We do not know whether NOP1(sym2, anti1)⊆N F IN, but we conjecture that this is true. 5 Lower Bounds At any step of the computation, each copy of an object can be in one of the two possible regions: in region 1 or in the environment. This is a kind of “1-bit memory”, and the only way this memory can influence the following computation is by a cooperative transport rule: moving this object to the other region together with moving another object in the same or opposite direction. Therefore, it is expected that the number set generated by such P systems is “continuous”, i.e., the distance between any two neighboring numbers is bounded. More formally, let us use the following notion: the segments (finite segments of arithmetic progression with difference k) are defined as SEGk={{n+ki |0≤ i≤m} | n, m ≥0} ∪ {∅}. For instance, SEG1is the class of all sets of consecutive numbers, while SEG2is the class of all sets of consecutive even numbers and all sets of consecutive odd numbers. Example 1. ∅ ∈ NOP1(sym1, anti1)∩NOP1(sym2). Consider a P system Π0= (O={b}, E =∅, µ = [1]1, w1=b, R ={(b, in), (b, out)}, i0= 1). There is one possible computation: object boscillates between region 1 and the environment, so the set of results of the halting computations is empty. This system only uses symport rules of weight 1, so it belongs to both OP1(sym1, anti1) and OP1(sym2). Example 2. NOP1(sym1, anti1)⊇SEG1. 32 A. Alhazov, Yu. Rogozhin Fix the numbers m, n ≥0. Consider a P system Π1= (O={a, b}, E ={a}, µ= [1]1, w1=anbm, R ={(b, out),(b, out;a, in)}, i0= 1). Any computation of Π1halts in at most one step: every object bexit region 1, in exchange for either an object aor for nothing. This is why the computation halts, with region 1 containing ncopies of object ainitially present there, and some number iof copies of athat were brought inside. Notice that 0 ≤i≤m, and every number is possible. Thus, N(Π1) = {n+i|0≤ i≤m}. Since m, n were chosen arbitrary, together with the previous example we obtain the result we claim: SEG1can be generated. Example 3. NOP1(sym2)⊇SEG1∪SEG2. Fix the numbers m, n ≥0. Consider P systems Π2= (O={a, b}, E =∅, µ = [1]1, w1=an+mbm, R ={(b, out),(ab, out)}, i0= 1), Π3= (O={a, b}, E = ∅, µ = [1]1, w1=an+2mb2m, R ={(bb, out),(ab, out)}, i0= 1). Any computation of Π2halts in at most one step: every object bexit region 1, together with either an object aor for nothing. This is why the computation halts, with region 1 containing n+mcopies of object ainitially present there, except some number jof copies of athat were taken outside. Notice that 0 ≤j≤m, and every number is possible. Substituting j=m−i, 0 ≤i≤m, we obtain (n+m)−(m−i) = n+i. Thus, N(Π2) = {n+i| 0≤i≤m}. System Π3has a similar behavior, except there are 2mobjects binitially present in region 1, and some number 2iof them leave region 1 in pairs, 0 ≤i≤m, while each of the others comes into the environment together with an object a. The number of objects aremaining in the system is (n+ 2m)−(2m−2i) = 2i. Therefore, N(Π3) = {n+ 2i|0≤i≤m}. In this way, SEG1∪SEG2can be generated by systems Π2and Π3for all possible numbers m, n, together with Π0. 6 Extensions It might be interesting to distinguish between the different objects obtained in region 1 when the system halts, thus obtaining vectors instead of numbers (in the notations, Nis replaced by P s). It might be also interesting to allow the environment to initially contain also some objects in finite multiplicities (extended environment; let us denote this feature with eenv). One of the common features of segments introduced above is that of “continuity”: there exists a number ksuch that the graph defined by numbers of the set as nodes, where two nodes iand jare adjacent if |i−j| ≤ q, is connected. Let us define the distance between two vectors as a sum of absolute values of differences of their components. Then the notion of continuity can be extended to vector sets in the natural way: a vector set Mis k-continuous if any two vectors in Mbelong to some sequence of vectors in M, such that the neighboring vectors of this sequence Minimal Cooperation in Symport/Antiport P Systems with One Membrane 33 have distance at most k. Choose a number n. Below is an example of a P system with one membrane and transport rules of minimal cooperation that generates a vector set which is not n-continuous. Example 4. (discontinuity for vectors) Consider Π4= (O={a, b, c, d}, E =∅, µ = [1]1, w0=bncndn+1, w1=an, R, i0= 1), where R={(a, out;b, in),(a, out;c, in),(a, out;d, in),(d, out;d, in), (bc, out),(bc, in)}Consider a halting computation of Π4. First, each object amust exit region 1, exchanged either for bor c(otherwise dwill come inside the system and the computation will never halt). Then, the only way to make rules (bc, out), (bc, in) inapplicable is to separate object band c, and this can only be done in the first step by the first two rules, and only if one of them is applied ntimes and the other one is not applied. Therefore, when Π4halts, region 1 will either contain bn or cn. The distance between the two resulting vectors is 2n. Notice that we took advantage of extended environment, and of both forms of minimal cooperation. We suppose that this result cannot be achieved with only one form of minimal cooperation, so we conjecture that P sOP1(sym2, anti1, eenv)6= PsOP1(sym1, anti1, eenv)∪PsOP1(sym2, eenv). 7 Conclusions and Open Questions The generative power of the first two classes of one-membrane communicative P systems with minimal cooperation considered above is between the class of finite number sets and the class of finite segments of arithmetic progressions (with difference 1 for OP1(sym1, anti1) and differences 1,2 for OP1(sym2)). It is still open what are the exact bounds, but we conjecture that NOP1(sym1, anti1) = SEG1and NOP1(sym2) = SEG1∪SEG2because, informally, the fact that the objects have “1-bit memory” can only influence one elementary decision. It is interesting to consider the class of P systems with both forms of minimal cooperation: OP1(sym2, anti1). Does it generate more than SEG1∪SEG2? Does it only generate finite languages? We are unable to answer these questions, but we conjecture answer to the latter one is positive. Finally, the similar questions were not studied much for the extensions, like allowing the environment to initially also have finite multiplicities of some objects. Does this extension increase the generative power of P systems with minimally cooperative communication and one membrane? We do not know the answer to these questions, but we conjecture that NOP1(sym1, anti1, eenv)⊆NF IN and NOP1(sym2, eenv)⊆NF IN are true, i.e., while using only one form of cooperation, the generated number sets are still finite. 34 A. Alhazov, Yu. Rogozhin Acknowledgements The first author is supported by the project TIC2002-04220-C03-02 of the Research Group on Mathematical Linguistics, Tarragona. Both authors acknowledge the Moldovan Research and Development Association (MRDA) and the U.S. Civilian Research and Development Foundation (CRDF), Award No. MM2-3034. References 1. A. Alhazov, R. Freund, Yu. Rogozhin: Some optimal results on symport/antiport P systems with minimal cooperation. In Cellular Computing. Complexity Aspects (M.A. Guti´errez-Naranjo, Gh. P˘aun, M.J. P´erez-Jim´enez, eds.), F´enix Editora, Sevilla, 2005, 23–36. 2. A. Alhazov, M. Margenstern, Yu. Rogozhin, V. Rogozhin, S. Verlan: Communicative P systems with minimal cooperation. In Membrane Computing. International Workshop WMC 2004, Milan, Italy, 2004, Revised Selected and Invited Papers (G. Mauri, Gh. P˘aun, M.J. P´erez–Jim´enez, G. Rozenberg, A. Salomaa, eds.), LNCS 3365, Springer-Verlag, Berlin, 2005, 161–177. 3. A. Alhazov, Yu. Rogozhin, S. Verlan: Symport/antiport tissue P systems with minimal cooperation. In Cellular Computing. Complexity Aspects (M.A. Guti´errezNaranjo, Gh. P˘aun, M.J. P´erez-Jim´enez, eds.), F´enix Editora, Sevilla, 2005, 37–52. 4. P. Frisco, H.J. Hoogeboom: P systems with symport/antiport simulating counter automata. Acta Informatica, 41, 2-3 (2004), 145–170. 5. A. P˘aun, Gh. P˘aun: The power of communication: P systems with symport/antiport. New Generation Computing, 20, 3 (2002), 295–306. 6. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002.