Particular Results for Variants of P Systems with One Catalyst in One Membrane

Particular Results for Variants of P Systems with One Catalyst in One Membrane Rudolf Freund Faculty of Informatics Vienna University of Technology Favoritenstr. 9–11, A–1040 Vienna, Austria [email protected] Summary. Purely catalytic P systems can generate all recursively enumerable sets of natural numbers with only three catalysts in one membrane, whereas we know that one catalyst in one membrane is not enough. On the other hand, P systems also allowing (non-catalytic) non-cooperative evolution rules with only two catalysts in one membrane are already computationally complete, too. We here investigate special variants of P systems with only one catalyst in one membrane that are not computationally complete, i.e., variants of P systems with only one catalyst in one membrane that cannot generate all recursively enumerable sets of natural numbers. 1 Introduction P systems with catalysts were already introduced in the original paper on membrane systems in [10], with the additional feature of using priority relations on the rules and proved to be computationally complete; in [15], [16] it was shown that priority relations on the rules are not necessary to obtain this completeness result. In [7] it finally was shown that P systems with only one membrane can generate any recursively enumerable set of natural numbers (when not counting the catalysts in the membrane) with only two catalysts. On the other hand, in [8] [purely] catalytic P systems (where all evolution rules are catalytic ones) were introduced and from results obtained in [6], [15] it was observed that seven catalysts are enough if we only allow rules with catalysts; in [7], even three catalysts were shown to be sufficient. As in [8] catalytic P systems with one catalyst in one membrane were shown not to be able to generate all recursively enumerable sets of natural numbers, the main open questions remaining are the computational power of catalytic P systems with two catalysts in one membrane and the corresponding question for P systems with one catalyst in one membrane (obviously, P systems with no catalyst and only non-catalytic non-cooperative rules in one membrane cannot generate all recursively enumerable sets of natural numbers; in fact, as an 42 R. Freund immediate consequence of Theorem 1 we see that exactly the regular sets can be generated). In the following section, after some prerequisites from formal language theory, we define the specific variants of P systems with catalysts considered in this paper. In the main part of the paper we show particular results proving that specific variants of P systems with one catalyst in one membrane cannot generate all recursively enumerable sets of natural numbers; unfortunately, the main problems, i.e., the computational power of P systems with one catalyst in one membrane and of catalytic P systems with two catalysts in one membrane remain unsolved. 2 Definitions For well-known notions and basic results from the theory of formal languages, the reader is referred to [4] and [14]. We only give some basic notations first. By Nwe denote the set of non-negative integers (i.e., natural numbers). In the following, two sets of natural numbers are considered to be equal if they only differ at most by 0. By NRE we denote the set of all recursively enumerable sets of natural numbers, and by NREG the set of all regular sets of natural numbers. 2.1 Multiset Grammars In this paper we consider several types of multiset grammars (various interesting models of grammars for generating multisets of objects were considered in [9], multiset automata were investigated in [3]). In fact, we could also define the corresponding types of grammars generating strings which then are interpreted as multisets. In the following, a multiset of objects will simply be represented by any string containing exactly the same number of each object as the multiset. Amultiset grammar is a construct G= (V, T, P, S) with Vbeing a set of symbols (or objects), T⊂Vis the set of terminal symbols (terminal objects),S∈V−Tis the start symbol, and Pis a (finite) set of multiset productions of the form u→vwith uand vbeing multisets over V. The application of the production u→vto a multiset xhas the effect of replacing the multiset ucontained in xby the multiset v. We consider all derivations starting from the multiset Sand using productions from Pand finally yielding a terminal multiset (i.e., a multiset only consisting of objects from T); the set of terminal multisets generated in that way is denoted by L(G). If all productions in Pare of the form A→vwith A∈V, then Gis called context-free. Arandom context multiset grammar is a construct Particular Results for P Systems with One Catalyst in One Membrane 43 G= (V, T, R, S) with the rules in Rbeing of the form A→v|(P, Q) where A→vis a context-free multiset production and Pand Qare disjoint subsets of V; the application of the rule to a multiset xhas the effect of replacing an object Afrom xby the multiset v, but only if all objects from Pappear in x(permitting contexts) and no object from Qoccurs in x(forbidden contexts). Again we consider all terminal derivations starting from Sand using rules from R, and we denote the set of terminal multisets generated in that way by L(G). If all the rules in Rare of the form A→v|(∅, Q), i.e., we only have forbidden contexts, then Gis called a forbidden random context multiset grammar. As multisets over a one-letter alphabet Vcorrespond with natural numbers, the set of multisets L(G) generated by a (random context) multiset grammar with a one-letter terminal alphabet can be seen as the corresponding set of natural numbers, and we denote the sets of natural numbers generated by context-free multiset grammars, random context multiset grammars, and forbidden random context multiset grammars by NCF,NRC, and NfRC, respectively. It is well known (e.g., see [9]) that NCF =NREG; moreover, from the results known for the corresponding families of string languages, we immediately infer NfRC $NRE (e.g., see [5]). 2.2 The Standard Model of (Catalytic) P Systems The standard type of membrane systems (P systems) has been studied in many papers and several monographs; we refer to [2], [5], [10], [11], and [12] for motivation and examples. In the definition of the P system below we omit all ingredients (like priority relations on the rules) not needed in the following. AP system (of degree d, d ≥1)is a construct Π= (V, C, µ, w1, . . . , wd, R1, . . . , Rd, io), where: (i) Vis an alphabet; its elements are called objects; (ii) C⊆Vis a set of catalysts; (iii)µis a membrane structure consisting of dmembranes (usually labeled with i and represented by corresponding brackets [iand ]i,1≤i≤d); (iv)wi,1≤i≤d, are strings over Vassociated with the regions 1,2, . . . , d of µ; they represent multisets of objects present in the regions of µ(the multiplicity of a symbol in a region is given by the number of occurrences of this symbol in the string corresponding to that region); (v) Ri,1≤i≤d, are finite sets of evolution rules over Vassociated with the regions 1,2, . . . , d of µ; these evolution rules are of the forms a→vor ca → cv, where cis a catalyst, ais an object from V−C, and vis a string from ((V−C)× {here, out, in})∗; 44 R. Freund (vi)iois a number between 1 and dand it specifies the output membrane of Π. The membrane structure and the multisets represented by wi,1≤i≤d, in Π constitute the initial configuration of the system. A transition between configurations is governed by an application of the evolution rules which is done in parallel: all objects, from all membranes, which can be the subject of local evolution rules have to evolve simultaneously (maximally parallel derivation mode). The application of a rule u→vin a region containing a multiset Mresults in subtracting from Mthe multiset identified by u, and then in adding the multiset identified by v. The objects can eventually be transported through membranes due to the targets in and out (we usually omit the target here). We refer to [2] and [12] for further details and examples. According to [8], the P system Πis called catalytic, if every evolution rule involves a catalyst. The system continues maximally parallel derivation steps until there remain no applicable rules in any region of Π; then the system halts. We consider the number of objects from Vcontained in the output membrane ioat the moment when the system halts as the result of the underlying computation of Π, but in contrast to the original definitions we do not take into account the catalysts. The set of results of all halting computations possible in Πis denoted by N(Π).The set of all sets of natural numbers computable by P systems/(purely) catalytic P systems (as the numbers of objects different from the catalysts to be found in the output membrane ioat the end of halting computations) of the above type with d membranes and the set of catalysts containing at most melements is denoted by N−cOPd(catm) and N−cOPd(pcatm), respectively. 2.3 Specific Variants of P Systems The results we elaborate in the following section are formulated for P systems with only one membrane, hence, we can omit the membrane structure and describe the P system in the following way, where wdenotes the initial multiset and Rthe set of rules in the membrane: Π= (V, C, w, R). Now let us consider P systems of that kind where in addition the set Vis divided into three disjoint subsets V0, V 00,and V000 such that the rules in Robey to the following constraints: •for a∈V0, there exists no rule in Rwith aon the left-hand side; •for a∈V00, the rules in Rare of the form ca →cv with c∈Cand v∈ (V0∪V00)∗; •for a∈V000, the rules in Rare of the form a→vwith v∈(V0∪V000 )∗. P systems fulfilling all the requirements stated above are called 1-separated, and the corresponding family of sets of natural numbers generated by such P systems is denoted by N−cOP1(sepcatm). Particular Results for P Systems with One Catalyst in One Membrane 45 The main idea of 1-separated P systems is that catalytic rules and non-catalytic rules are separated with respect to the symbols they generate and therefore cannot interfere, i.e., the objects generated by catalytic rules cannot be affected by noncatalytic rules and vice versa. If we relax the third condition stated above for 1-separated P systems and allow the non-catalytic rules to be of the most general form a→vwith v∈V∗, then these P systems are called weakly 1-separated and the corresponding set of sets of natural numbers generated by such P systems is denoted by N−cOP1(wsepcatm). The only restriction remaining in the case of weakly 1-separated P systems is that “catalytic objects” a∈V00 cannot generate “non-catalytic objects” a∈V000, yet this feature already will allow us to show that N−cOP1(wsepcatm)$NRE (see Theorem 1). Another quite simple restriction is to require that there is no object such that the only rules affecting this object are catalytic ones. This requirement guarantees that if a symbol cannot be taken by a catalytic rule then it will be affected by a noncatalytic rule (observe that we are working in the maximally parallel derivation mode). We shall call P systems with catalysts in only one membrane obeying to this condition 1-complete. The corresponding set of sets of natural numbers generated by 1-complete P systems is denoted by N−cOP1(complcatm). 3 Results We first cite some well-known results from [7]: N−cOP1(cat2) = N−cOP1(pcat3) = NRE. Moreover, from [8] we know that N−cOP1(pcat1)$NRE, hence, for catalytic P systems, the main open question remained if N−cOP1(pcat2) were already computationally complete, too. In the following, we now investigate the generative power of the specific variants of P systems with one catalyst in one membrane as defined in the preceding section. Theorem 1 NREG =N−cOP1(cat0) = N−cOP1(sepcat1) = N−cOP1(wsepcat1). Proof. As N−cOP1(cat0)kNREG is obvious and well-known and, moreover, the inclusions N−cOP1(cat0)jN−cOP1(wsepcat1)jN−cOP1(sepcat1) are clear from the definitions, we only have to prove N−cOP1(wsepcat1)jNREG. Now let Π= (V, {c}, w, R) be a weakly 1-separated P system with only one catalyst cand with the rules in Rfulfilling the condition that the objects appearing on the right-hand side vof a catalytic rule ca →cv can only be affected by a catalytic rule. Moreover, according to the definition of weakly 1-separated P systems given above, the set Vis divided into three disjoint subsets V0, V 00 ,and V000 such that the rules in Robey to the following constraints: 46 R. Freund •for a∈V0, there exists no rule in Rwith aon the left-hand side; •for a∈V00, the rules in Rare of the form ca →cv with c∈Cand v∈ (V0∪V00)∗; •for a∈V000, the rules in Rare of the form a→vwith v∈V∗. Then we construct a context-free multiset grammar G= ((V−V0)∪ {S},{d}, P, S) with d, S being new objects not contained in Vand Pcontaining the following multiset productions •S→h(w); •a→h(v), for a∈V00 and the rule ca →cv in Rwith c∈Cand v∈(V0∪V00)∗; •a→h(v), for a∈V000 and the rule a→vin Rwith v∈V∗; the morphism h:V→ {d} ∪ V00 ∪V000 is defined by •h(a) = dfor a∈V0, and •h(a) = afor a∈V00 ∪V000. Obviously, Ggenerates the same results as Π: by the definition of weakly 1- separated P systems, the objects generated by catalytic rules can only be affected by catalytic rules; for the application of the catalytic rules the maximally parallel derivation mode has no regulating effect, because all the possible evolutions of the catalytic objects from V00, even those generated at some time by the non-catalytic rules, can be simulated sequentially by the multiset grammar G; on the other hand, as we only consider halting computations in Π, the possible evolutions of the non-catalytic objects from V000 in Πcan be simulated sequentially in G, too, because there is no regulating interplay with the objects from V00 . On the other hand, each derivation in Gyields a result – represented by the number of terminal symbols d– that can also be obtained as the result – represented by the number of terminal objects from V0– of a halting maximally parallel derivation in Π. These observations complete the proof. ut Theorem 2 N−cOP1(complcat1)jNfRC. Proof. We start with the 1-complete P system Π= (V, {c}, w, R), i.e., there is no object in Vsuch that the only rules in Raffecting this object are catalytic rules (observe that there must be symbols that are not affected by any rule, because otherwise no halting derivation would be possible), and then construct a forbidden random context multiset grammar G= (V∪V0 1∪V00 1∪ {S, X, Y, Z},{d}, P, S), V0={b|b∈V, there is no rule cb →cv ∈R and no rule b→v∈R}, V1=V−V0, V0 1={b0|b∈V1}, V00 1={b00 |b∈V1}, Particular Results for P Systems with One Catalyst in One Membrane 47 with d, S, X, Y, Z being new symbols not contained in V∪V0 1∪V00 1, and Pcontaining the following rules (as we are using only rules with forbidden context, we simply write A→v|Qinstead of A→v|(P, Q)): 1. S→h0(w)X|∅; h0is the morphism h0:V→V1∪ {d}with •h0(b) = bfor b∈V1and •h0(b) = dfor b∈V0 (we start with the control symbol Xand the morphic image of the axiom w where all terminal objects b∈V0from Πare replaced by the single terminal symbol dfrom G); 2. a→a00|V0 1∪V00 1∪ {S, Y, Z}for every awith a rule ca →cv ∈R (such a rule can only be applied once in the presence of the control symbol X); 3. X→Y|V0 1∪(V00 1− {a00})∪ {S, Y, Z}for every awith a rule ca →cv ∈R (after having introduced at most one symbol a00 in the presence of the control symbol X, the control symbol is changed from Xto Y); 4. a00 →h(v)|V0 1∪(V00 1− {a00})∪ {S, X, Z}for every awith a rule ca →cv ∈R and a→h(v)|V00 1∪ {S, X, Z}for every awith a rule a→v∈R; his the morphism h:V→V0 1∪ {d}defined by •h(b) = b0for b∈V1, and •h(b) = dfor b∈V0 (in the presence of the control symbol Y, first eventually the single symbol a00 has to be affected by simulating one of the corresponding catalytic rules and then for all other symbols b∈V1a non-catalytic evolution rule is simulated thereby replacing every terminal object b∈V0by the terminal symbol d); 5. Y→Z|V1∪V00 1∪ {S, X, Z} (if all symbols from V1are primed – after having applied at most one rule for a marked symbol a00 and rules for every other symbol b∈V1– we change the control symbol from Yto Z); 6. a0→a|V00 1∪ {S, X, Y }for every a∈V1 (we then rename the primed symbols to the corresponding non-primed ones until finally we get a multiset of symbols over V1∪ {d}and the control symbol Z); 7. Z→X|V0 1∪V00 1∪ {S, X, Y } (we now may start again with simulating another derivation step in Πby changing the control symbol from Zto X, or we may stop the derivation by using the next rule); 8. Z→λ|V1∪V0 1∪V00 1∪ {S, X, Y } (if the multiset only consists of terminal symbols d, we may erase the control symbol Zthus obtaining the same result for the number of terminal symbols as in the halting derivation in Π– there counting the number of objects from V0). 48 R. Freund The reader should observe that we can mark (with two primes) at most one symbol, but on the other hand we cannot enforce that this one symbol is marked in any case, which is the main reason why we have to demand the P system to be complete, i.e., if we do not simulate the catalytic rule, then the symbol will be affected by simulating a non-catalytic rule (which has to exist because of the completeness of the P system). In fact, it is easy to see that Gsimulates exactly the derivations in Π.2 Instead of solving the original problem concerning the computational power of P systems with one catalyst in one membrane, the results proved above give rise to new interesting problems, e.g., we may investigate the generative power of complete or (weakly) separated P systems with more than one catalyst in possibly more than one membrane. 4 Conclusion In this paper, specific variants of P systems with one catalyst in one membrane were shown not to be able to generate all recursively enumerable sets of natural numbers. For the original variant of P systems with one catalyst in one membrane, we also conjecture a similar result, but unfortunately were not able to prove it. The problem of the generative power of purely catalytic P systems with two catalysts in one membrane remains open, too. References 1. C.S. Calude, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: Multiset Processing – Mathematical, Computer Science and Molecular Computing Points of View. LNCS 223, Springer, Berlin, 2001. 2. C.S. Calude, Gh. P˘aun: Computing with Cells and Atoms. Taylor & Francis, London, 2001. 3. E. Csuhaj-Varj´u, C. Mart´ın-Vide, V. Mitrana: Multiset automata. In [1], 69–84. 4. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory. Springer, Berlin, 1989. 5. J. Dassow, Gh. P˘aun: On the power of membrane computing. J. of Universal Comput. Sci., 5, 2 (1999), 33–49. 6. R. Freund, M. Oswald, P. Sos´ık: Reducing the number of catalysts needed in computationally universal systems without priorities. In Fifth International Workshop Descriptional Complexity of Formal Systems (E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszil, eds.), Budapest, Hungary, July 12-14, 2003, MTA SZTAKI, Budapest, 2003, 102–113. 7. R. Freund, L. Kari, M. Oswald, P. Sos´ık: Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 330, 2 (2005), 251–266. Particular Results for P Systems with One Catalyst in One Membrane 49 8. Z. Dang, O. Egecioglu, O.H. Ibarra, G. Saxena: Characterizations of catalytic membrane computing systems. In 28th International Symposium on Mathematical Foundations of Computer Science 2003, MFCS 2003, Bratislava, Slovakia, August 25-29, 2003 (B. Rovan, P. Vojt´as, eds.), LNCS 2747, Springer, Berlin, 2003, 480–489. 9. M. Kudlek, C. Mart´ın-Vide, Gh. P˘aun: Toward a formal macroset theory. In [1], 123–134. 10. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 11. Gh. P˘aun: Computing with membranes: an introduction. Bulletin EATCS, 67 (1999), 139–152. 12. Gh. P˘aun: Membrane Computing: An Introduction. Springer, Berlin, 2002. 13. Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds.: Membrane Computing. International Workshop, WMC-CdeA 2002, Curtea de Arge¸s, Romania, August 2002, LNCS 2597, Springer, Berlin, 2003. 14. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, Springer, Berlin, 1997. 15. P. Sos´ık, R. Freund: P Systems without priorities are computationally universal. In [13], 400–409. 16. P. Sos´ık: The power of catalysts and priorities in membrane systems. Grammars, 6, 1 (2003), 13–24.