Further Results on P Systems with Promoters/Inhibitors

Further Results on P Systems with Promoters/Inhibitors Drago¸s Sburlan Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain and Faculty of Mathematics and Informatics Ovidius University of Constanta, Romania E-mail: [email protected] Summary. The paper gives several results regarding P systems with non-cooperative rules and promoters/inhibitors at the level of rules. For the class of P systems using inhibitors, generating families of sets of vectors of numbers, the equivalence with the family of Parikh sets of ET0L languages is presented. In case of P systems with noncooperative promoted rules even if an upper bound was not given, the inclusion of the family P sET 0Lwas proved. Moreover, a characterization of such systems by means of a particular form of random context grammars, therefore a sequential formal device, is proposed. 1 Introduction P systems with promoters/inhibitors represent a possible abstract mathematical model of several biological activities happening in a cell. For example, the mechanism of activating/deactivating enzymes by what is called phosphorization (the covalent attachment of phosphoryl to the enzyme) as well as the way the enzymes control different metabolic reaction chains, might be modelled by such systems. From a formal point of view we are interested to find properties of the languages generated by such bio-inspired devices. For the general case, when “weak” cooperative rules are considered, i.e., involving only one catalyst, the computational completeness of P systems with promoters/inhibitors was proved in [2] and [4]. Also, when the weight of promoters/inhibitors can be larger than one, universality results are obtained (see [1]). Here we deal with systems that use non-cooperative rules and promoters/inhibitors of weight one. Because only promoters/inhibitors cannot restrict the parallelism of a P systems with non-cooperative rules, as catalysts do for instance 290 D. Sburlan in the case of catalytic P systems, the common accepted conjecture was that such systems are not computational complete. In this paper, we give an answer to the problem regarding the computational capability of the family of P systems with inhibited non-cooperative rules; the case when promoted non-cooperative rules are used is left open. In Section 2 we present basic notions and results regarding Lindenmayer systems and random context grammars. In addition, for the random context grammar, we define a new restrictive form – random context grammars with limited checking – and we show that such grammars can generate strictly more than the family of languages generated by ET0L systems. We conjecture that such systems are not computationally complete. In Section 3 we prove that any P system using inhibitors can finish its computation having all membranes empty except the output one. Moreover, we show that such P systems generate exactly the same family of Parikh sets as ET0L systems. This result has a certain importance not only from formal languages point of view, but also from a biological perspective because, for instance, the membership and reachability problems for ET0L systems are decidable. In Section 4 we give a lower bound for the family of sets of vectors generated by P systems with non-cooperative promoted rules, namely the family of Parikh images of ET0L languages. In what concerns the upper bound, we give a characterization by means of random context grammars with limited checking. In this way, an open problem arises about the maximal parallel computing by means of a sequential machine. Along the paper, several open problems and research proposals are also presented. 2 Preliminaries Here we recall several notions from the classical theory of formal languages, namely Lindenmayer systems and random context grammars. For further details regarding these notions we refer to [6], [3], and [7]. 2.1 Lindenmayer Systems A 0L system is a triple H= (V, P, ω), where Vis a finite alphabet, Pis a set of context-free rules over V, and ω∈V∗is the axiom. The set of rules Phas to be complete, i.e., for each symbol a∈Vthere must be at least one rule a→α∈P with this letter aon the left-hand side. 0L systems use parallel derivations, i.e., xdirectly derives yin a 0L system H= (V, P, ω), with x, y ∈V∗, written as xOL =⇒Hy, if x=x1x2. . . xn,y=y1y2. . . yn, where xi∈V,yi∈V∗, and xi→yi∈P, 1 ≤i≤n. A T0L system is a triple H= (V, T, ω), where Vis a finite alphabet, T= {T1, . . . , Tk}is a finite set of tables over V, where each table Ti, 1 ≤i≤kis a Further Results on P Systems with Promoters/Inhibitors 291 complete set of context-free rules over V, and ω∈V∗is the axiom. We say that xdirectly derives yin a T0L system H= (V, T, ω), with x, y ∈V∗, written as xT OL =⇒Hy, if xOL =⇒Hiyfor some i, 1 ≤i≤k, with the 0Lsystem Hi= (V, Ti, ω). An ET0L system is a quadruple H= (V, T, ω, ∆), where H= (V, T, ω) is a T0L system, and ∆∈V,∆6=∅, is the terminal alphabet. In an ET0L system H= (V, T, ω, ∆), xdirectly derives y, with x, y ∈V∗, written as xET OL =⇒Hy, if xT OL =⇒Hy. The transitive and reflexive closure of ET OL =⇒His denoted by ET OL =⇒∗H. The language generated by the system H(denoted by L(H)) is L(H) = {w∈ ∆∗|ω ET OL =⇒∗Hw}. Thus in an ET0L system only words over a distinguished sub-alphabet are in the generated language. A language is said to be an ET0L language if there is an ET0L system generating it. A 0L system is a TOL system that has only one table. Adding a number of tables yields an infinite hierarchy of subclasses of the class of T0L languages. In turn, every ET0L language can be generated by an ET0L system with only two tables. We have that for any ET0L system Hthere exists an equivalent ET0L system H= (V, T, ω, ∆) such that V=VN∪∆,VN∩∆=∅, and each rule from Ti∈T, 1≤i≤ |T|, is in one of the forms A→α,A∈VN,α∈V∗or a→a,a∈∆. We will denote by ET 0Lthe family of languages generated by ET0L systems. 2.2 Random Context Grammars A random context grammar is a quadruple G= (N, T, P, S), where N,T,Sare defined as in the context-free grammars and Pis a finite set of random context rules, that is, triples of the form (A→α, Q, R) where A→αis a context-free rule with A∈N,α∈(N∪T)∗, and Q, R ⊆N. For x, y ∈(N∪T)∗we write xrc =⇒yiff x=x1Ax2,y=x1αx2for some x1, x2∈(N∪T)∗, (A→α, Q, R) is a triple in P, all symbols of Qappear and no symbol of Rappears in x1Ax2. We will refer Qas the permitting context and Ras the forbidding context of the rule A→α. If the forbidding context is empty for every rule, then we speak about a random context grammar without appearance checking. The language generated by a random-context grammar G= (N, T, P, S) is L(G) = {v∈T∗|S rc =⇒∗v}, where by rc =⇒∗we have denoted the transitive and reflexive closure of rc =⇒. We denote by RCλ ac the family of languages generated by random-context grammars with appearance checking and λrules. The following result stands: RCλ ac =RE. For any random context grammar with appearance checking and λrules there exists an equivalent random context grammar with appearance checking and λ rules G0= (N0, T 0, P0, S0) such that for the rules (A→α, Q, R)∈P0we have |α| ≤ 2, |Q| ≤ 1, |R| ≤ 1. Definition 1. A random context grammar with limited checking and λrules is a random context grammar G= (N, T, P, S)with rules of the form (A→α, Q, R), 292 D. Sburlan where A→αis a context-free rule with A∈N,α∈(N∪T)∗, and Q, R ⊆N, |Q|+|R| ≤ 1. We denote by RCλ lc the family of languages generated by random context grammars with limited checking and λrules. A natural question arise: Open Problem: what is the generative power of random context grammars with limited checking? Conjecture. Random context grammars with limited checking are not universal, i.e., RCλ lc ⊂RE. One can remark that this is a “winning” problem irrespective which is its answer, since if such grammars prove to be universal, then even if Theorem 5 become trivial, we will have a new normal form for random context and matrix grammars with appearing checking, but if they are not universal, then, as we will see, this implies that P systems with promoters are not universal. We also suggest an approach that might be useful for proving the non-universality of catalytic P systems with only one catalyst. Anyway, random context grammars with limited checking are strictly more powerful than ET0L systems. Theorem 1. RCλ lc ⊃ET0L. Proof. Consider an ET 0Lsystem H= (V, T, ω, ∆) such that V=VN∪∆,VN∩∆= ∅,T={T1, T2, . . . , Tk}and all rules from Ti, 1 ≤i≤kare in one of the forms A→α,A∈VNα∈V∗, or a→a,a∈∆. We will simulate the computation of the system Hwith a random context grammars with limited checking G= (NG, TG, PG, SG). Since in Hthe rules a→a,a∈∆, do not affect the derivation process, we can remove them from tables. Therefore, let Ti={A(i,j)→α(i,j)|1≤j≤ri}, 1≤i≤k, be the sets of rules representing the ET0L tables. We denote: NG= (V\∆)∪ {ti,j |1≤i≤k, 1≤j≤2∗ri+ 1}∪{A|A∈V\∆} TG=∆. We define the set of rules PGas follows. (S→t(i,1)ω, ∅,∅),with 1 ≤i≤k. The starting symbol Sis non-deterministically changed into one table selector (t(i,1), 1 ≤i≤k) and the string ωrepresenting the axiom of the ET0L to be simulated. Next we have the following rules that correspond to the rules of the tables: (A(i,j)→α(i,j),{t(i,j)},∅),with 1 ≤i≤k, 1≤j≤ri. Further Results on P Systems with Promoters/Inhibitors 293 Basically, each rule produces “colored” (overlined) symbols in the presence of symbol t(i,j), 1 ≤i≤k, 1 ≤j≤ri, representing the selected table. The next task needed for a correct simulation is to check whether or not all symbols in the current sentential form were actually transformed into overlined ones. In order to accomplish this task we have the rules: (t(i,j)→t(i,j+1),∅,{Ai,j }),with 1 ≤i≤k, 1≤j≤ri. In fact, there are needed even a smaller number of rules of the above type. This is due to the fact that our system might contain more rules with the same symbol on the left-hand side. However, the reason for adopting such numbers was just for having a simpler notation. In case there are still remaining not overlined symbols, a symbol t(i,ri+1), 1 ≤ i≤k, 1 ≤j≤ri, is not produced. We also have the rules: (A(i,j)→A(i,j),{t(i,ri+1)},∅),1≤i≤k, 1≤j≤ri. Their role is to change back the overlined symbols into regular ones. Now, in order to simulate the selection of a new table and to iterate the process, we have to be sure that all overlined symbols have been changed back into regular ones. The procedure is accomplished, in a similar way, by the rules: (t(i,j)→t(i,j+1),∅,{A(i,j−ri)}),1≤i≤k, ri+ 1 ≤j≤2∗ri. Finally, if everything worked as we expected (recall that the simulation is nondeterministic and if the derivation went in a “wrong” way, then it is blocked), then we have produced a symbol t(i,ri+1), 1 ≤i≤k. Next, we can use this symbol to repeat the table selection mechanism or to stop non-deterministically the generative core. These actions are achieved by making use of the rules: (t(i,2∗ri+1) →t(h,1),∅,∅),with 1 ≤i, h ≤k, (t(1,2∗ri+1) →λ, ∅,∅). Because we consider in the language only terminal strings, we have L(H) = L(G), hence the inclusion RCλ lc ⊇ET0Lis proved. In order to prove that the inclusion is strict we have to construct a language that cannot be generated by an ET0L system. To this aim, we construct G= (V, T, P, S) that generates the language {(anb)m|m≥n≥1}defined as follows: •V={S, A, B, C, D, X, Y, N, N0, P, P0, P 00, R, Q, Z, a, b}, •T={a, b}, •Pcontains the following rules: 294 D. Sburlan (S→AX, ∅,∅) (P0→P00,∅,{A}) (A→BB, {X},∅) (P00 →Q, ∅,{N0}) (X→Y N, ∅,{A}) (C→bD, {Q},∅) (B→A, {Y},∅) (Q→R, ∅,{C}) (Y→X, ∅,{B}) (D→C, {R},∅) (X→P, ∅,∅) (R→Q, ∅,{D}) (A→aC, {P},∅) (Q→Z, ∅,{C}) (P→P0,{N0},∅) (D→λ, {Z},∅) (N→N0,∅,∅) (Z→λ, ∅,∅) (N0→λ, ∅,∅) The details concerning the way this grammar works are left to the reader. Consequently, we have RCλ lc ⊃ET0L.2 3 Non-cooperative P Systems with Inhibitors In this section we consider P systems with symbol objects, non-cooperative rules, inhibitors at the level of rules, and generating sets of vectors of numbers. The family of sets of vectors generated by systems with at most m≥1 membranes is denoted by P sPm(ncoo, inhR). In order to prove the main result of the section, that is PsPm(ncoo, inhR) = P sET 0L, we will accomplish the following plan: •show the equivalence between P systems with non-cooperative inhibited rules using mmembranes, and P systems with non-cooperative inhibited rules and only one membrane; •show that any P system with non-cooperative inhibited rules is equivalent with a P system with non-cooperative inhibited rules having the alphabet made out of two disjoint sets, the set of terminals and of nonterminals; in addition, all rules have a non-terminal on their left-hand side; moreover, the set is complete, i.e., for each nonterminal there exists at least one rule having it on the left-hand side; •for a given set of inhibited rules, define saturated classes of rules, i.e., find the sets containing rules that does not mutually forbids each other; •show that P sPm(ncoo, inhR) = P sET 0Lby double inclusion. Here is how we proceed: Theorem 2. P sPm(ncoo, inhR) = P sP1(ncoo, inhR), for m≥2. Proof. The inclusion P sPm(ncoo, inhR)⊇P sP1(ncoo, inhR) is trivial. For the proof of the inclusion P sPm(ncoo, inhR)⊆P sP1(ncoo, inhR), we construct a P system Π1= (V, C, µ, w, R, ϑ) that simulates the computation of P system Πm= (V , C, µ, w1, . . . , wm, R1, . . . , Rm, ϑ) in the following way. First, denote by L={1,2, . . . , m}the set of labels of the regions in Πm. Then, we define: •V={ai|a∈V , i ∈ L}. Further Results on P Systems with Promoters/Inhibitors 295 •C=C=∅; Let h:V∗× L → V∗be a mapping such that 1) h(a, i) = ai, a ∈V , i ∈ L; 2) h(λ, j) = λ, for all j∈ L; 3) h(x1x2, j) = h(x1, j)h(x2, j), x1, x2∈V∗,j∈ L. •denote by w=h(w1)h(w2). . . h(wm), where wiis the multiset present in region i∈ L of Πmat the beginning of the computation. •Ris defined as follows. For each rule a→α|¬b∈Ri,a, b ∈V,αis a string over {c, cout, cin |c∈V},i∈ L, we add to Rthe rule h(a, i)→α0|¬h(b,i)where α0is the corresponding string over {h(c, i), h(c, j), h(c, k)|c∈V , i, j, k ∈ L},jbeing the label of the outer region of i, and kbeing the label of the inner region of i. •ϑ= 1; In other words, for the P system with a single region that simulates a P system with mregions, we have encoded the regions labels into objects (the subscript associated to an object indicates the region where the corresponding object belongs) and we have expressed the rules of regions by the corresponding encoded objects. In this way we ensured that, when simulating Πmwith Π1, both the parallelism at the level of regions and at the level of whole system Πmis respected. In addition, one can remark that whenever Πmhalts, Π1halts as well. Moreover, when Π1 halts, we will have in the output region of Π1all the objects corresponding to the multisets present in all regions of Πm. However, in the output multiset wΠ1of Π1 we can distinguish the output multiset wΠmof Πmbecause we know which are the objects corresponding to the output region of Πm(they are the objects that have as index ϑ). Therefore, we have to delete the unnecessary objects that remain in the output region of Π1in a halting configuration since we want to show that Π1 and Πmgenerate exactly the same set of vectors of numbers. We will modify the rules presented above in the following manner. We add to the vocabulary Va new symbol D(the object Dstands for the “deletion command”) and we replace each rule ai→α0|¬bi∈Rby ai→α0D|¬bi∈R, and each rule ai→α0∈Rby ai→α0D∈R, respectively. In addition, we add the following rules D→λ, ai→λ|¬D, for all ai∈V,i6=ϑ One can remark that in this way we produce at each computational step at least 296 D. Sburlan one object Dand also, in the same time, we delete the already existing object(s) D. If there exist rules that can be executed (i.e., there will be objects D) rules of type ai→λ|¬Dcannot be applied. When the computation halts, objects Dare not produced anymore, and so, the deletion rules can start and erase the remaining unnecessary objects. Consequently we have shown that both systems generate the same family of vectors of natural numbers, hence we have PsPm(ncoo, inhR)⊆ PsP1(ncoo, inhR). 2 As a consequence of the proof above we have the following corollary: Corollary 1. For any P system Πwith inhibited non-cooperative rules there exists an equivalent P system Π0with inhibited non-cooperative rules such that, for any halting configuration of Π0, all regions of Π0, excepting the output one, are empty. Remark 1. Later we will show that P systems with inhibited non-cooperative rules generate exactly PsET 0L. Therefore, one can prove the above result also by using the fact that the family ET0Lis closed under arbitrary morphisms (so we can delete the unnecessary objects in a halting configuration). Now, let us define the non-excluding inhibiting relation and saturated sets with respect to this relation. First, for a given alphabet V, let R={r1, r2, . . . , rk}be a set of productions of the form ri: (Ai→αi|¬Bi), Ai, Bi∈V,Ai6=Bi,αi∈V∗, 1 ≤i≤k. For a rule r: (A→α|¬B)∈Rwe define left(r) = Aand inh(r) = B. Two rules ri, rj∈Rare said to be in the non-excluding inhibiting relation, and we denote this by ri≡nei rj, iff left(ri)6=inh(rj) and left(rj)6=inh(ri). Remark 2. We have the following properties: • ≡nei is reflexive (obvious), • ≡nei is symmetric (obvious), • ≡nei is not transitive. For example, take R={r1: (A→α|¬B), r2: (D→β|¬C), r3: (B→γ|¬A)}. Observe that r1≡nei r2,r2≡nei r3, but r16≡nei r3. Definition 2. A subset W⊆Ris said to be saturated (or complete) with respect to non-excluding inhibiting relation ≡nei iff (∀)ri, rj∈W,ri≡nei rj, and (∀)ri∈ R\W, (∃)rj∈Wsuch that ri6≡nei rj. Remark 3. The set Rmay contain more saturated subsets, say W1, W2, . . . , Wk, with respect to the non-excluding inhibiting relation ≡nei. We have W1∪W2∪ . . . ∪Wk=Rand Wi∩Wj, 1 ≤i, j ≤k, not necessarily empty. Example 1. Consider the following set of rules R={r1: (A→α1|¬B), r2: (C→α2|¬D), r3: (B→α3|¬D), r4: (A→α3|¬C), r5: (D→α4|¬C)}. Then we have: Further Results on P Systems with Promoters/Inhibitors 297 W1:W2:W3:W4: r1: (A→α1|¬B)r3: (B→α3|¬D)r1: (A→α1|¬B)r2: (C→α2|¬D) r2: (C→α2|¬D)r4: (A→α3|¬C)r4: (A→α3|¬C)r3: (B→α3|¬D) r5: (D→α4|¬C) Lemma 1. For any P system Π1= (V , C, µ, w, R, ϑ)with non-cooperative rules and inhibitors there exists an equivalent P system Π1= (V, C, µ, w, R, ϑ)with non-cooperative rules and inhibitors such that: V=VN∪VT, VN∩VT=∅, C=C=∅, µ=µ= [ ]1, w⊆VN, R={r1, . . . , rk},is a set of rules of the form A→α|¬B or A→α, where A, B ∈VN, α ∈V∗, ϑ= 1. Proof. (Sketch) We define the set VN={A|a∈V} ∪ {D}and VT=V. The set of rules is defined as: R={A→ΦD |a→φ∈R, A, D ∈VN, Φ ∈V∗ N} ∪ {A→ΦD|¬B|a→φ|¬b∈R, A, B, D ∈VN, Φ ∈V∗ N} ∪ {D→λ} ∪ {A→a|¬D|A, D ∈VN, a ∈VT} where by Φwe understand the image of φthrough a morphism that maps all regular letters from Vto corresponding capital letters. Basically we detect when the system halts and only at that time we change the nonterminals into terminals. 2 Remark 4. A similar result stands also for P systems with non-cooperative rules and promoters. Of course, both results can be extended to P systems having m membranes and not with only one membrane as we have considered. Lemma 2. For any P system Π1= (V , C, µ, w, R, ϑ)with non-cooperative rules and inhibitors given in the form specified by Lemma 1 there exists an equivalent P system Π1= (V, C, µ, w, R, ϑ)with non-cooperative rules and inhibitors such that the set of rules Ris complete (i.e., for each A∈Vthere exists at least one rule of type A→α∈Ror A→α|¬B∈R). Proof. (Sketch) Assume that in Rthere is no rule with object Bon its left-hand side. (i.e., there are no rules of type B→βor B→β|¬C). In addition, assume that object Bis produced by rules of type A→αB or A→αB|¬C. Also, suppose there is at least one rule of type A→α|¬B. 304 D. Sburlan In this way we have shown that random context grammars with limited checking are able to simulate P systems with promoted non-cooperative rules. 2 5 Conclusions We have defined a particular form of random context grammars, namely random context grammars with limited checking. We have proved that such grammars can generate strictly more than the family ET0L. Even if it was not proved whether or not the random context grammars with limited checking are as powerful as Turing machines, they are still useful when characterizing P systems with non-cooperative inhibited rules. Moreover, we conjecture that such grammars can be used to give an upper bound for the family of sets of vectors generated by P systems with noncooperative rules and one catalyst. We have shown that P systems with inhibited non-cooperative rules generate the same Parikh sets as ET0L systems, therefore we have for “free” all the proved properties of this classical formalism. In addition, we have proved that for each P system with non-cooperative promoted (or inhibited) rules there exists an equivalent P system that halts having all the regions empty, except the output one. Several open problems are mentioned along this work. Acknowledgments This work was done while the author was funded by AECI, Spanish Ministry of Foreign Affairs. The author is very thankful to all colleagues from the Research Group on Natural Computing, University of Seville for providing a very good scientific atmosphere. References 1. A. Alhazov, D. Sburlan: Ultimately confluent rewriting systems. Parallel multiset– rewriting with contexts. Submitted 2004. 2. P. Bottoni, C. Mart´ın-Vide, Gh. P˘aun, G. Rozenberg: Membrane systems with promoters/inhibitors. Acta Informatica, 38, 10 (2002), 695–720. 3. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory. Springer- Verlag, Berlin, 1989. 4. M. Ionescu, D. Sburlan: On P systems with promoters/inhibitors. JUCS, 10, 5 (2004), 581–599. 5. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 6. G. Rozenberg, A. Salomaa: The Mathematical Theory of L Systems. Academic Press, New York, 1980. 7. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. Springer-Verlag, Berlin, 1997.