Time-Driven Computations in P Systems

Time-Driven Computations in P Systems Matteo Cavaliere1, Claudio Zandron2 1Microsoft Research - University of Trento Centre for Computational and Systems Biology, Trento, Italy [email protected] 2Universit`a degli Studi di Milano - Bicocca Dipartimento di Informatica, Sistemistica e Comunicazione Via Bicocca degli Arcimboldi 8, 20126 Milano, Italy [email protected] Summary. It is a well-known fact that the time of execution of a (biochemical) reaction depends on many factors, and, in particular, on the current situation of the whole system. With this motivation in mind, we propose a model of computation based on membrane systems where the various rewriting rules have different times of execution and, moreover, the time of execution of each rule can vary during the computation, depending on the configuration of the whole system (in this sense, the computation is “time-driven”). We show that such systems are universal in a very simple framework: a regular time-mapping suffices to obtain universality for systems with minimal cooperation (one catalyst). 1 Time-Driven Computations In [3] a new class of membrane systems, called timed membrane systems have been introduced. The main idea of timed membrane systems (called also timed P systems) is to associate, via a mapping, to each rule of the system a certain time of execution. The motivations for this model come from the fact that, in a living cell, different chemical reactions may take different times to be executed. Actually, the time of execution of a chemical reaction may not be a constant but can change according to the state of the system where the reaction takes place. For instance, a reaction can be executed in a faster or slower way if certain substances are present. Motivated by this fact, it is natural to consider a model of timed P systems where the time of execution of the rules changes dynamically, according to the state of the system. In fact, it is quite common in biochemical experiments to control the whole reaction process by modifying the conditions in which the system operates, in order to speed-up certain reactions and to delay other reactions. In this way, one can safely assume that some reactions will take place only when some chemicals have been produced or consumed by other processes. We formalize this notions by introducing contents-timed P system, that is, P systems where the time of execution of the rules is defined by a mapping depending 134 M. Cavaliere, C. Zandron on the contents of the regions of the system; in other words, the time of execution depends on the current configuration of the system. We prove that time can indeed be a powerful resource for computation, when it can be “programmed” and it is used together with maximal parallelism: universality can be obtained with a quite simple system, using a regular time-mapping and a single catalyst. The rest of the paper is organized as follows. In Section 2 we give all formal language notions we will use in the paper. In Section 3 we formally define contentstimed P systems and we gives some preliminary results. In Section 4 we show how a time-driven P system works, by means of an example. Then, in Section 5 we give a universality results for time-driven P systems with regular time mappings. We conclude the paper with Section 6, where some open problems and directions for future research are given. 2 Formal Languages Preliminaries We will shortly recall the main elements of formal language theory used in the paper. For more detailed information the reader can consult the standard books and monographs in the area (as, for instance, [4], [8], and [7]). As usual, V∗denotes the set of all strings over the alphabet V. For a∈V and x∈V∗we denote by |x|athe number of occurrences of ain x. Then, for V={a1, . . . , an}, the Parikh mapping associated with Vis the mapping on V∗ defined by ΨV(x) = (|x|a1, . . . , |x|an) for each x∈V∗. The family of recursively enumerable languages is denoted by RE, and the family of Parikh images of RE languages is denoted by P sRE (this is the family of all recursively enumerable sets of vectors of natural numbers). The family of all recursively enumerable sets of natural numbers is denoted by NRE. The multisets over a given finite support (alphabet) are represented here by strings of symbols. The order of symbols does not matter, because the number of copies of an object in a multiset is given by the number of occurrences of the corresponding symbol in the string. A context-free programmed grammar with appearance checking is a construct G= (N, T, S, P), where N(T, resp.) is a finite set of nonterminals (terminals, resp.), S∈Nis the start symbol, and Pis a finite set of productions of the form (b:A→u, Eb, Fb), where bis a label, A→uwith A∈Nand u∈(N∪T)∗is a context-free production, and Eb, Fbare two sets of labels of productions of G(Eb is called the success field and Fbthe failure field of the production). A production (b:A→u, Eb, Fb) is applied as follows: if Ais present in the sentential form, then the production is applied and the next production to be applied is chosen from those with the labels in Eb, otherwise, the sentential form remains unchanged and we choose the next production from the rules labeled by some element of Fb. A derivation step is denoted by ⇒while ⇒∗denotes the reflexive and transitive closure of ⇒. Time-Driven Computations in P Systems 135 If no failure field is given for any of the productions, then we obtain a programmed grammar without appearance checking. We denote the set of labels as Lab(P) = {b|(b:A→u, Eb, Fb)∈P}. Also, for A∈N, we define l(A) = {b|(b:A→u, Eb, Fb)∈P}. In this paper we use the following normal form for programmed grammars with appearance checking. Theorem 1. For any programmed grammar G[with appearance checking] there exists a programmed grammar G0[with appearance checking, respectively] such that there is a unique initial production applied (with label l0), the last production applied in G0is an erasing production Z→λ(with label lh) and L(G0) = L(G). The unsuccessful derivations in G0halts in sentential forms from Z(N∪T)∗if G0is without appearance checking, or from (N∪T)∗N(N∪T)∗if G0is with appearance checking. By PR we denote the family of languages generated by programmed grammars without appearance checking, and by P Rac we denote the family of languages generated by programmed grammars with appearance checking. Proofs of the following results can be found in [4]. Theorem 2. CF ⊂P R ⊂P Rac =RE. 3 Contents-Timed P Systems As mentioned in the Introduction, a contents-timed P system is essentially a P system where the time of execution of the rules depends on the configuration in which they are applied. We start from the standard definition of P system with symbol-objects and catalytic, non-cooperative evolution rules (we suppose the reader familiar with the notions of P systems, as, for instance, presented in [6]; many further information concerning P systems (including an up–to–date bibliography) can be found in [9]). Definition 1. A P system (of degree m≥1) with symbol-objects is a construct Π= (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0), where: •Ois the alphabet of Π; its elements are called objects; •C⊆Vis the set of catalysts; •µis a membrane structure consisting of mmembranes labeled 1,2, . . . , m; •wi,1≤i≤m, specifies the multiset of objects present in the corresponding region iat the beginning of a computation; 136 M. Cavaliere, C. Zandron •Ri,1≤i≤m, are finite sets of evolution rules over Oassociated with regions 1,2, . . . , m of µ; the rules can be non-cooperative, that is, of the form a→v, where ais an object from O−Cand vis a string over {ahere, aout, ainj|a∈ O−C, 1≤j≤m}, or they can be catalytic rules, of the form, ca →cv, where ais an object from O−C,vis a string over {ahere, aout, ainj|a∈O−C, 1≤ j≤m}, and c∈Cb; if the target indication is not specified, then it is intended to be here; •i0∈ {0,1, . . . , m}is the output region; if i0= 0, then it indicates the environment. Aconfiguration of Πcan be represented by a string of parentheses (the structure µ) and strings over O(contents of the regions). For instance, a possible configuration of the system Πwith alphabet O={a, b}and structure µ= [1[2]2]1 is represented by the string: [1aab[2a]2]1. Given a string wrepresenting a configuration, then all the strings obtained from wby taking any permutation of the strings representing the contents of the regions or exchanging (with their associated contents) two regions present at the same level, still represent the same configuration. When we say that a configuration I∈L, where Lis a set of strings, we mean that Iis one of the configurations represented by the strings present in L. Given the system Πwe denote by I(Π) the set of strings representing all the possible configurations of the system (not only the reachable ones, i.e., the ones reached during a possible evolution of the system Π). We consider a contents time-mapping ethat fixes the time of execution of a rule given a certain configuration. Formally, e: (R1∪R2∪ · · · ∪ Rm)×I(Π)−→ N. We suppose the mapping complete, that is, defined for each pair (r, I), r∈R1∪ R2∪ · · · ∪ Rm, I ∈I(Π). Now, joining the system Πand the mapping e, it is possible to construct a contents-timed P system Π(e) as (O, C, µ, w1, . . . , wm, R1, . . . , Rm, i0, eid) working in the following way. We suppose the existence of an external global clock that ticks at uniform intervals, taken as time unit, starting at time 0. With each region of the system a finite number of objects and a finite number of evolution rules are associated. At each time in the regions of the system we have together rules in execution and rules not in execution; at each time, all the rules that can be started in each region have to be applied. If a rule r∈Ri,1≤i≤m, is applied, then all objects that can be processed by the rule have to evolve by this rule (a rule is applied in a maximally parallel manner as standard in P systems area). When a rule ris started at step j, and the current configuration of the system is I, then the execution of rterminates at step j+eid(r, I). Time-Driven Computations in P Systems 137 If two rules start at the same time, then possible conflicts for using the occurrences of symbol-objects are solved by assigning the objects in a non-deterministic way (again, in the way usually defined in P systems area). Notice that when the execution of a rule ris started, the occurrences of symbolobjects used by this rule are not anymore available for other rules during the entire execution of r. The computation halts when no rule can be applied in any region and there are no rules in execution (that is, the system reaches a halting configuration). The output of a halting computation is the vector of numbers representing the multiplicities of objects present in the output region in the halting configuration. Collecting all the vectors obtained, for all possible halting computations, we get the set P s(Π(e)) of vectors of natural numbers generated by the system Π(e). We say that the time-mapping eis regular if it can be calculated by using a monadic transducer, that is, a finite state automaton with a label associated to each state, as defined in [2]. As in [2], we will indicate only the time-mapping and not the monadic transducer that implements it. The reader can find more details in [2], but as general idea, the monadic transducer that implements a time-mapping reads, like a finite state automaton, the configuration Iof the system followed by the label of the rule r, and produces (outputs) the label associated to the state where it halts. This label represents the time of execution of the rule r, when the system is in the configuration I, that means e(I, r). In what follows we will use only regular time-mappings, even if the idea can be easily extended to more general time-mappings. Therefore, we use the following notation TPsPm(α, reg), α ∈ {ncoo} ∪ {catk|k≥0}, to denote the family of sets of vectors of natural numbers generated by contentstimed P systems with at most mmembranes, evolution rules that can be noncooperative (ncoo) or catalytic (catk), using at most kcatalysts (as usual ∗is used if the corresponding number of membranes or catalysts/bi-stable catalysts is unknown) and a regular time-mapping. In [3] a special class of P systems is defined. A P system is called time-free if it generates always the same set of vectors, independently of the time-mapping used. The following Theorem can be found in ([1]). Theorem 3. Every P system with non–cooperative rules is time-free. In fact, each computation of such a system can be described by a tree, in which the result of a computation is stored in the yield, and such that the length of an application of a rule to an object is represented by the length of the corresponding edge. Thus, it is clear that the result of the computation, obtained on the leaves of the tree, does not depend on the length of the edges in the tree itself. This is also true even in the case when the same rule on the same object could require, in different moment, a different number of steps to be executed. 138 M. Cavaliere, C. Zandron Therefore, since P systems with symbol-objects and non-cooperative evolution rules generate exactly PsCF (see, e.g., [6]), it follows that Theorem 4. TP sPm(ncoo, reg) = P sCF, m ≥1. 4 Time-Driven Computations: An Example While time does not “help” in case of systems using only non-cooperative evolution rules (Theorem 4), the situation is clearly different when a minimal amount of cooperation is introduced. In fact, the following example shows that a contents-timed P system using one occurrence of one catalyst and a regular time-mapping can generate the Parikh image of a non-semilinear language. Π= (O, µ = [1[2]2]1, w1=λ, w2=Acb, R1, R2, i0= 1), where: O={A, a, A0, A00, b, b0, b00 , b000 , c, b0 h, b00 h, b000 h,#}, R1=∅, R2={r1:A→A0A0, r2:A→aout, r3:A0→A00, r4:A00 →A} ∪ {r5:cb →cb0b00, r6:b0→b000, r7:cb00 →c, r8:cb000 →cb, r9:b000 →#} ∪ {r10 :cb →cb0 hb00 h, r11 :cb00 h→c, r12 :b0 h→b000 h, r13 :b000 h→#, r14 :cb000 h→c} ∪ {r15 : # →#}. The time mapping eis defined as follows. e(rj, I) = 1, for each rj, j ∈ {1,2,3,4,5,6,8,9,10,12,13,14}and any I∈I(Π). e(r7, I) = ½1 if I∈ {[1λ[2cb0b00w]2]1, w ∈(A0)+} 2else e(r11, I) = ½1 if I∈ {[1w[2cb0 hb00 h]2]1, w ∈(a)+} 2else The contents-timed P system Π(e) generates the Parikh image of the language {a2n|n≥1}. In fact, the computation starts with region 1 empty (it is the output region) and region 2 containing the multiset Acb. The rule r1takes care of the duplication of the objects A. In case the duplication is not done in the correct way, then the entire computation is trashed by using the change in run-time of the execution time of rule r7, according to the defined time-mapping e. The change in run-time of the execution time of rule r11 is used to check that the system halts in a correct way. Notice that all the rules, except r7and r11 have an execution time always fixed to be one step. Time-Driven Computations in P Systems 139 Suppose that in region 2, at certain step k−1, there is the multiset Ai, for some ithat is a power of two, together with objects cand b. Suppose now that, at step k−1, all the occurrences of Aare changed by applying the rule r1while cand bare rewritten by using the rule r5. The next configuration obtained (at step k; the rule applied last one step) will contain the multiset (A0)i+1, and the objects c,b00 and b0in region 2, while region 1 remains empty. Now at step kthe rule r7is applied, together with the rule r3and r6. Because, at step k, the system contains only A0and c, b00, b0, then, for definition of the used time-mapping, the rule r7lasts exactly one step. Therefore, at step k+ 1, the system will contain the multiset (A00)i+1 and the objects cand b000 in region 2, while region 1 is still empty. In the next step all the objects A00 are changed to Aby using the rule r4while, at the same time, the objects cand b000 are rewritten to cand b, by using the rule r8(both rules take one step to be executed). The initial configuration is obtained again, the number of Ahas been duplicated, and the process can be iterated. In case the duplication of objects Ahas not been done in the correct way, then the entire computation is trashed. In fact, suppose that at step k−1 some of the occurrences of Aare changed to A0by rule r1, while some of them are changed to aand sent out to region 1 by rule r2. Then, in the same step, objects cand bare rewritten to objects c,b00 and b0by rule r5. At step k(rules r1, r2, r5take one step to be executed) the system contains some A0and objects c,b00 and b0in region 2 and some ain region 1. Now the rules r3and r7, r6are applied, but because of the time-mapping used, and because of the configuration of the system at step k, the rule r7takes two steps to be executed. Therefore at step k+ 1, object b000 is produced, but because the catalysts cis still busy by rule r7, the rule r9is used, object # is produced and the computation is non-halting. The correct halting of the system is guaranteed from the presence of rule r10 and rules r11, r12. In fact, suppose that in region 2, at step k−1, there is the multiset Ai, for some ithat is a power of two, together with objects cand b. To halt the system it is necessary to apply the rule r10. At the same time all the objects Aneed to be changed in aand sent to region 1, by using rule r2. In the next step k, the system contains the multiset aiin region 1, and objects c,b00 h,b0 h in region 2. The computation will halt in two more steps by using rules r12 and r11 that will last exactly one step and finally rule r14. If not all the objects Aare changed to ain the step k−1, then some of them are changed to A0by using rule r1, and therefore, at step k, the system will contain some ain region 1, some A0in region 2, together with objects c,b00 hand b0 h. At step k, the rule r11 and r12 are started, but because of the current configuration, rule r11 lasts two steps, while r12 lasts only one step. Then, objects b000 his produced at step k+ 1, while catalyst cis still busy by rule r11. Therefore rule r13 is used, object # produced and the computation cannot halt. This guarantees that the system halts in a correct way and with a number of objects ain the output region that is a power of 2. 140 M. Cavaliere, C. Zandron 5 Time-Driven Universality It is possible to show even more than in the example presented in Section 4: a P system using a regular time-mapping and only one occurrence of one catalyst is universal, in the sense that it can generate the family of Parikh images of recursively enumerable languages. As in the previous example, the non-cooperative rules implement the rewriting of the objects, while the catalytic rules check that the rewriting is done in the correct way. If this does not happen, the time of execution of the catalytic rules is set in such a way that the computation does not halt. The proof is based on the simulation of programmed grammars with appearance checking. Theorem 5. TP sP (cat1, reg) = P sRE. Proof. We show that, for every programmed grammar G= (N, T, S, P) with appearance checking is possible to construct a P system Π, using one catalyst, and a regular time-mapping e, such that P s(Π(e)) is exactly the Parikh image of L(G). We use the morphism hdefined as h(a) = a0, a ∈N, and h(a) = aout, a ∈T. We suppose that Gis in the normal form presented in Theorem 1. We construct the following P system. Π= (O, µ = [1[2]2]1, w1=λ, w2=l0SX1cX2h, R1, R2, i0= 1), where: O=N∪T∪N0∪T0∪Lab(P)∪Lab0(P)∪Lab(P) ∪ {#, c, h, h0, X1, X0 1, X2, X0 2, X00 1, X00 2, h0}, R1=∅, R2={r1:li→λ, r2:l0 i→li, li→li|li∈Lab(P)} ∪ {A→h(u)l0 j|(li:A→u, Eli, Fli)∈P, lj∈Eli} ∪ {r3:A0→A|A∈N} ∪ {A→A|A∈N} ∪ {h→h0, h →h, r4:h0→h, r5:h→h} ∪ {X1→X0 1, X1→X00 1, cX00 1→cX1, cX2→cX0 2, r6:cX0 2→cX00 2, X00 2→X2} ∪ {X00 1→#,#→#}, where N0and T0are obtained by priming the symbols in Nand T, respectively, and Lab0(P) and Lab(P) are obtained from Lab(P) by priming and overlining the symbols in Lab(P). The regular time-mapping eis defined as follows. Let R0be the set {r1, r2, r3, r4, r5}. Then e(r, I) = 2,for r∈R0,and e(r, I) = 1 for r∈R2−R0, I ∈I(Π). The time-mapping for r6is then fixed in the following way. Time-Driven Computations in P Systems 141 e(r6, I) =                    1 if I∈ {[1w[2w0lil0 jh0X0 1cX0 2]2]1 |li, lj∈Lab(P), lj∈Eli, w0∈(N∪N0)∗, w ∈T∗} ∪{[1w[2w0lil0 jhX0 1cX0 2]2]1 |li, lj∈Lab(P), lj∈Fli, w0∈((N∪N0)−A))∗, w ∈T∗, (li:A→u, Eli, Fli)∈P} ∪{[1w[2Zlil0 hh0X0 1cX0 2]2]1|w∈T∗} 2 otherwise. The idea of the proof is simple: non-cooperative evolution rules of Πsimulate the productions of G, the catalytic evolution rules, together with the appropriate regular time-mapping ecan be used to check that the grammar productions are applied in the correct order, and this is done very much in the spirit of the example shown in Section 4 (one catalyst is then enough). Notice that some of the rules are labeled, some of them with the same label (when it is not necessary to distinguish them in the time-mapping). The “critical” rule whose time is modified in an appropriate way is r6: the time of execution is fixed to be 1 if a correct configuration is reached (grammar productions applied correctly), otherwise is fixed to be 2, and this brings to a non-halting computation (# is produced). The rules A→h(u)l0 jsimulates the productions of G. Each rule, when applied, produces the symbol l0 jthat indicates the next production to simulate. The role of r1is to guarantee that the productions are applied or skipped in the correct way. Therefore, the time of execution of r1is fixed in an appropriate way by e. In particular: The configurations of Πrepresented by the strings in the set {P[1w[2w0lil0 jh0X0 1cX0 2]2]1|li, lj∈Lab(P), lj∈Eli, w0∈(N∪N0)∗, w ∈T∗} correspond to all (and only) the configurations obtained when a production of G (the one with label li) has been correctly simulated (ljis the label of the next production to apply). The configurations represented by the strings in the set {[1w[2w0lil0 jhX0 1cX0 2]2]1|li, lj∈Lab(P), lj∈Fli, w0∈((N∪N0)−A))∗, w ∈T∗, (li:A→u, Eli, Fli)∈P} correspond to all (and only) the configurations obtained when the production of Gwith label lihas been correctly skipped (appearance checking) and the next production to apply is the one with label lj. Finally the strings in the set {[1w[2Zlil0 hh0X0 1cX0 2]2]1|w∈T∗} correspond to the configurations where the next production to simulate is the one with label lh(that, recalling the normal form of G, there should not be nonterminals).