P Systems with Antiport Rules for Evolution Rules

P Systems with Antiport Rules for Evolution Rules Rudolf FREUND, Marion OSWALD Faculty of Computer Science Vienna University of Technology Favoritenstr. 9–11, A–1040 Vienna, Austria E-mail: {rudi,marion}@emcc.at Abstract. We investigate a variant of evolution-communication P systems where the computation is performed in two substeps. First, all possible antiport rules are applied in a non-deterministic, maximally parallel way, moving evolution rules across membranes. In the second substep, evolution rules are applied to suitable objects in a maximally parallel way, too. Thus, objects can be the subject of change, but are never moved themselves. As result of a halting computation, we consider the multiset of objects present in a designated output membrane. When using catalytic evolution rules, we already obtain universal computational power with only one catalyst and one membrane. For systems without catalysts we obtain a characterization of the Parikh images of ET0L languages. 1 Introduction P systems were introduced in [8] as bio-inspired computing devices that work in a parallel and distributed way (see [9] for a comprehensive overview and [11] for actual developments in the area). In [1], a variant called evolution-communication P systems was investigated, combining evolution and communication rules for objects. Following this idea but moving evolution rules instead of objects, P systems with symport/antiport of rules were presented in [2]. We here take a similar approach: starting from the initial configuration of a P system with antiport rules for evolution rules, a transition from one configuration to the next one is, other than in [2], performed in two substeps: in the first substep evolution rules can be interchanged across a membrane by antiport rules (that are assigned to the membranes, see e.g., [6]), whereas in the second substep, objects can evolve by evolution rules in a maximally parallel manner. This means that in this model only the evolution rules but no objects are moved. If the computation halts, i.e., neither antiport nor evolution rules can be applied anymore, the result is given as the multiset of objects present in the output membrane. In the following section we first give some preliminary definitions and recall some notions for graph-controlled grammars, the computation model we use for proving the results elaborated in this paper; in the third section we introduce P systems with antiport rules for evolution rules. In the fourth section we show that when using purely catalytic evolution rules (i.e., every evolution rule involves a catalyst, as introduced in [7]), the 183 introduced systems can simulate graph-controlled grammars quite easily, which proves their universal computational power. A characterization of Parikh sets of ET0L languages is obtained when considering systems without catalysts, which is shown in section five where we also give an illustrative example. A short summary and an outlook to future research conclude the paper. 2 Preliminary Definitions The set of non-negative integers is denoted by N. An alphabet Vis a finite non-empty set of abstract symbols. Given V, the free monoid generated by Vunder the operation of concatenation is denoted by V∗; the empty string is denoted by λ, and V∗\{λ}is denoted by V+. A multiset over Vis represented as string over V(and any of its permutations); a set over Vis represented as a string, too, but with each element of Voccurring at most once. By |x|we denote the length of the word xover Vas well as the number of elements in the multiset represented by x. Agraph-controlled grammar is a construct G= (N, T, Lab, S, R, {1},{n}), where Ndenotes the set of non-terminals, Tis the set of terminal symbols, Lab ={1, ..., n} is the set of labels, Sis the start symbol, Ris a finite set of rules that can be represented as a function from Lab to P×2Lab ×2Lab, where Pdenotes the set of all context-free productions over the set Nof non-terminal symbols and the set of terminal symbols T. A rule in Rusually is written in the form (i:p(i), σ (i), ϕ (i)) , where σ(i) is called the success field and ϕ(i) is called the failure field of the rule labelled by i; the context-free production p(i) is of the form A(i)→w(i),where A(i)∈N and w(i)∈(N∪T)∗.Without loss of generality we not only assume that N∩Lab =∅ and that there is only one initial label (i.e., 1) and only one final label (i.e., n, with σ(n) = ϕ(n) = ∅), but we also may assume that if a computation has reached the final label n, then the obtained sentential form is terminal, i.e., it must not contain any nonterminal symbol. Finally, again without loss of generality we may also assume that in the case of a string language, the terminal symbols are generated by Gexactly in the correct sequence as they form a terminal word. All these features of a normal form for graph-controlled grammars, for example, follow from the constructions and results proved in [5], Theorem 6. An ET 0Lsystem is a construct GL= (V, T, t1, ..., tn, w) where Vis the alphabet,T⊆V is the terminal alphabet, and we define N:= V\T;ti,1≤i≤n, are lists of context-free rules that are called tables and w∈V∗is the axiom. All tables have to fulfill the condition that for every a∈Vthere is at least one production in ti,1≤i≤n. A derivation step in the ET0L system consists of the parallel application of the rules in one of the tables ti.The language generated by GLconsists of all terminal words being derivable from the axiom win an arbitrary number of derivation steps using the tables ti. The family of all languages of Parikh vectors generated by ET0L systems is denoted by PsET0L. 184 Aprogrammed ET0Lsystem is a pair (GL, σ),where GL= (V, T, t1, ..., tn, w) is an ET0L system and σis a function which to each table ti,1≤i≤n, assigns a finite subset of the set of tables. The language L(GL) of a programmed ET0L system GLconsists of all words xwhich have a derivation w=⇒ ti1 w1=⇒ ti2 w2=⇒ ti3 ... =⇒ tin−1 wn−1=⇒ tin wn=x such that tij+1 ∈σ¡tij¢for 1 ≤j < n. The family of all languages of Parikh vectors generated by programmed ET0L systems is denoted by P sEpT 0L. According to Theorem 8.3 in [3], PsET 0L=P sEpT 0L. For more details on formal language theory we refer to [10] and [3]. 3 P Systems with Antiport Rules for Evolution Rules AP system with antiport rules for evolution rules is a construct Π defined as follows: Π = (O, C, R, l, µ, w1, ..., wm, R1, ..., Rm, i0), where: •Ois an alphabet of objects; •Cis a set of catalysts and O∩C=∅; •Ris a finite set of evolution rules; •l:L→Ris an injective labelling of the rules in R;Lis called the set of labels with L∩(O∪C) = ∅; •µis a membrane structure with mmembranes bijectively labelled by 1, ..., m; •wi,1≤i≤m, are finite multisets over Otogether with finite sets over L(altogether represented as strings over O∪L) associated with the regions 1, ..., m of µ; •Ri⊆R, 1≤i≤m, are finite sets of antiport rules that are associated with the membranes 1, ..., m of µof the form (j, in;k, out),where j, k are sets of labels of evoution rules from R. •i0is the label of the output membrane. The rules in Rican easily be represented in a more depictive way: for (i, in;j, out)∈Rk we simply write i¿ k j. If we list the antiport rules of Π in this depictive way, instead of the sequence R1, ..., Rmwe only include the set RAcontaining the list of antiport rules. The weight of an antiport rule (i, in;j, out) is defined as max {|i|,|j|} . In the environment we assume every label of an evolution rule to occur. The initial configuration of such a system consists of µas well as of w1, ..., wm.A transition from one configuration to the next one is performed in two substeps: 185 1. The antiport rules from R1, ..., Rm(respectively RA) are applied in a non-deterministic maximally parallel way across all membranes; 2. The evolution rules are applied to suitable objects in a non-deterministic maximally parallel way within all membranes (using the catalysts in a multiset manner). As long as either antiport rules or evolution rules can be applied, the system proceeds performing these two substeps. Only if neither antiport rules nor evolution rules can be applied anymore, we say that the systems halts and consider the multiset of objects present in the designated output membrane in the final configuration to be the result (a non-halting computation does not produce a result). According to [7] (also see [4]), the P system with antiport rules for evolution rules Π is called catalytic, if every evolution rule involves a catalyst. The family of recursively enumerable Parikh sets generated by P system with antiport rules for evolution rules with mmembranes and kcatalysts (counted in the multiset sense over the whole system) and with the weight of the antiport rules being at most l is denoted by PsOP Am(catk, antil) ; if only catalytic evolution rules are used, we write PsOP Am(purecatk, antil) ; if k= 0,we simply write P sOPAm(antil) ; if one of the parameters k, l or mis not bounded, it is replaced by ∗. 4 Catalytic P Systems with Antiport Rules for Evolution Rules Theorem 1 Let L⊆Nk, k ≥1,be a recursively enumerable set of (vectors of) nonnegative integers. Then Lcan be generated by a P system with antiport rules for purely catalytic evolution rules in one membrane using one catalyst, i.e., PsOP A1(purecat1) = P sRE. Proof. Let G= (N, T, Lab, S, RG,{1},{n}) be a graph-controlled grammar. Then we construct the P system with antiport rules for evolution rules Π simulating Gas follows. We start with the initial configuration containing a catalyst c, the start symbol Sand an additional object Zas well as the labels for three evolution rules r0, r, r0, where rintroduces the trap symbol # that causes an infinite loop by r0, whereas r0simply starts the simulation of a derivation in G. Moreover, we define an injective mapping l:L→Rso that every production in RGhas a different label in l. c S Z r:cZ →c# r0:c#→c# r0:cZ →cZ 1 Figure 1: Initial configuration of Π. 186 The simulation of a derivation in Gworks as follows. We start from the initial configuration that is illustrated in figure 1. To simulate a rule (i:p(i), σ (i), ϕ (i)) ,where p(i) is of the form A(i)→w(i), A (i)∈Nand w(i)∈(N∪T)∗,we take the labelled evolution rules ei:cA (i)→cw as well as bi:cA (i)→c# and proceed as follows. •To start a simulation we take e 1¿ 1 r0as well as b 1¿ 1 r0. •To be able to communicate the correct sequence of evolution rules, we need the following antiport rules in RA: 1. es¿ 1e tas well as bs¿ 1 re tfor s∈σ(t)\ {n}. 2. res¿ 1b tas well as bs¿ 1b tfor s∈ϕ(t)\ {n}. 3. f¿ 1 re tas well as f¿ 1b tfor the case that the final label nis either in σ(t) or in ϕ(t),where f:cZ →c. In sum, we obtain the following P system with antiport rules for evolution rules Π : Π = (V, {c}, R, l, [1]1, cZSrr0r0, RA,1) , V=N∪T∪ {Z, #}, R={cZ →c#, c#→c#, cZ →cZ, cZ →c} ∪ {cA (i)→cw (i)|(i:A(i)→w(i), σ (i), ϕ (i)) ∈RG}, l={r:cZ →c#, r0:c#→c#, r0:cZ →cZ, f :cZ →c} ∪nei:cA (i)→cw (i),bi:cA (i)→c#|(i:A(i)→w(i), σ (i), ϕ (i)) ∈RGo, RA=½e 1¿ 1 r0,b 1¿ 1 r0¾ ∪½es¿ 1e t,bs¿ 1 re t|s∈σ(t)\ {n}, t ∈Lab¾ ∪½res¿ 1b t,bs¿ 1b t|s∈ϕ(t)\ {n}, t ∈Lab¾ ∪½f¿ 1b t,f¿ 1 re t|n∈σ(t)∪ϕ(t)¾. The simulation of the labelled productions of Gis controlled by the antiport rules assigned to membrane 1.If we guess that the rule labelled by iis applicable, we use ei, in the opposite case we take bi. If we have guessed that the rule labelled by iis applicable, then in order not to enter an infinite loop by using r:cZ →c#,eihas to be applied. If biis taken in, then the trap symbol # can only be avoided if no symbol A(i) occurs in membrane 1,but to guarantee the enforced application of bi(in contrast to the case ei) the rule rmust not be present. If in any moment the catalyst cis not used for eior is used for bi, then we immediately introduce the trap symbol # which leads to an infinite loop (using r0:c#→c#), hence no result is produced. On the other hand, whenever the final label nof Goccurs in either the success or the failure field of a production having just been applied, then we can assume that the obtained sentential form is already terminal (see section 2). Hence it is correct to halt after the elimination of the symbol Zby applying the evolution rule cZ →cwith the result being the objects contained in membrane 1. 187 In the original variant of catalytic P systems without antiport rules for evolution rules two catalysts in one membrane are needed if we also allow non-catalytic rules; for purely catalytic systems only allowing for catalytic rules, three catalysts are needed as shown in [4]. Considering strings as objects being affected by the evolution rules, we even need no catalysts: The same proof as above with just omitting the catalyst cshows that any recursively enumerable set of strings can be generated by a P system with antiport rules for evolution rules working on strings in only one membrane (at each substep where the evolution rules have to be applied, to each string only one evolution rule is applied, yet only if no rule is applicable the string remains unchanged). 5 P systems with Antiport Rules for Evolution Rules without Catalysts According to the original definition in [2] we consider the evolution rules occurring in the regions to be applied in a maximally parallel manner. Using (purely) catalytic rules, this parallelism is reduced, but as Theorem 1 shows this reduction of the parallelism yields maximal computational power. The importance of parallelism becomes visible when we deal with P systems with antiport rules for evolution rules without catalysts. In order to show the influence of parallelism we give a simple example of a P system with antiport rules for evolution rules without catalysts: Example 2 Consider the following P system Π : Π = (V, R, l, [1]1, S1, RA,1) , V={S, a}, R={S→SS, S →a}, l={(1, S →SS),(2, S →a)}, RA=½1¿ 1 1,2¿ 1 1¾. S1 1 Figure 2: Initial configuration of Π. From the initial configuration, which is also illustrated in figure 2, we start by applying an antiport rule from RA.Taking 1¿ 1 1does not change the actual configuration of the system, so that in the next substep the evolution rule S→SS can be applied. The system can go on by repeatedly carrying out these two steps, thereby each time doubling the occurrences of S. If in any moment the antiport rule 2¿ 1 1is used instead of 1¿ 1 1,then the rule S→ais brought into the system. In the next step, all objects Sare changed into a, and no further rule can be applied anymore, hence the system halts. 188 Observe that a rule occurring in a region has to be applied in the maximally parallel manner, hence, we obtain 2n, n ≥0,objects ain the final configuration. For P systems with antiport rules for evolution rules without catalysts we obtain a characterization of P sET0L, i.e., PsOP A∗(anti∗) = P sET 0L. This result will be proved in the following two lemmas: Lemma 3 P sET 0L⊆P sOPA1(anti∗). Proof. Let GL= (V, T, t1, ..., tn, w) be an ET0L system. Then we can construct a P system with antiport rules for evolution rules Π simulating GLin the following way: First we define two additional tables: t0={X→X|X∈V}, tn+1 ={X→X|X∈V\T}. We then define R=n+1 ∪ i=0 ti,which is the set of all context-free productions occurring in the tables ti,0≤i≤n+ 1. Now let mbe the cardinality of Rand L={0,1, ..., m, m + 1}.Moreover we define a bijective mapping l:L→R; hence, we can represent each table ti,0≤i≤n+ 1,by the corresponding word riover L(observe that ricontains any element of Lat most once and that |ri| ≥ card(V) for 0 ≤i≤n). We now define the P system with antiport rules for evolution rules Π simulating the ET0L system GL Π = (V, R, l, [1]1, wr0, RA,1) , with RA=½ri¿ 1 r0|1≤i≤n¾ ∪½rj¿ 1 ri|1≤i, j ≤n¾ ∪½rn+1 ¿ 1 ri|0≤i≤n¾. The label r0is just a dummy to allow us to start with the simulation of any of the tables from the ET0L system. The antiport rules in ½rj¿ 1 ri|1≤i, j ≤n¾allow us to continue with any arbitrary table tjafter the application of the table ti. Finally, the table rn+1 coming into action after the application of any of the antiport rules in ½rn+1 ¿ 1 ri|0≤i≤n¾ allows us to check for the appearance of non-terminal symbols from N. If the underlying sentential form in GLis terminal, then the corresponding configuration in Π halts. Hence, we have proved that the terminal derivations in GLexactly correspond to the halting computations in Π, which observation concludes the proof. Due to our definition of enforced substeps, we only need one membrane instead of two membranes needed for the corresponding result proved in [2]. 189 Example 4 Taking again the previous example, the corresponding ET0L system (with the constraint that every table has to contain at least one rule for each symbol) would be ({S, a},{a},{S→SS, a →a},{S→a, a →a}). According to the construction of the proof elaborated above, we would get the following P system with antiport rules for evolution rules: Π = (O, R, l, [1]1, S24, RA,1) , O={S, a}, R={S→SS, a →a, S →a, S →S}, L={1,2,3,4}, l={(1, S →SS),(2, a →a),(3, S →a),(4, S →S)}, RA=½12 ¿ 1 24,23 ¿ 1 24¾ ∪½12 ¿ 1 12,23 ¿ 1 12,23 ¿ 1 23,12 ¿ 1 23¾ ∪½4¿ 1 24,4¿ 1 12,4¿ 1 23¾. Lemma 5 P sOP A∗(anti∗)⊆PsEpT0L. Proof (Sketch). Let Π = (O, R, l, µ, w1...wm, RA, i0) be an arbitrary P system with antiport rules for evolution rules without catalysts. We now construct a programmed ET0L system GL= (V, T, t0, t1, ..., tn, w, σ) with V=O×H∪O∪ {#},where H={1, ..., m}is the set of membrane labels, T=O, taking into accout the following observations. •The contents of each membrane region in any configuration over Π can be represented as a string over the alphabet O×H. The notation (a, i) for a∈O, i ∈H, indicates that the object aoccurs in membrane region i. Moreover, for each i∈Hwe define the homomorphism hi:O→O× {i}such that hi(a) = (a, i) for all a∈O. •There is only a finite number of possible distributions of the evolution rules over the whole membrane structure. •It is easily decidable which of these distributions of evolution rules is reachable from the initial configuration. •For each reachable distribution of evolution rules, it is decidable which distributions are possible after applying the given antiport rules from Π in a maximally parallel manner. •For each reachable distribution dof evolution rules we now construct a table of context-free productions tdfor GLin the following way: td=t0 d∪t00 d∪e t; 190 t0 dcontains the context-free production hi(a)→hi(w) if and only if a→wis a rule contained in membrane iin the current distribution of evolution rules d; t00 dcontains the rule (a, i)→(a, i) if and only if there is no production in t0 dwith (a, i) on its left-hand side (this guarantees the completeness condition for the tables in the ET0L system GL); e t={a→a|a∈O∪ {#}} . •For every reachable distribution of evolution rules d, σ0(td) exactly contains all tables tesuch that eis reachable in one step from din Π. •To start the simulation of Π in GLwe encode the initial contents of all membrane regions in the initial configuration and use an additional table t0in GLwith t0={(a, i)→(a, i)|a∈O, i ∈H}and σ(t0) = {td0} where d0is the distribution of the evolution rules in the initial configuration. •For all dwith σ0(td)6=∅we take σ(td) = σ0(td).In that way the derivation steps in Π can be simulated in GL. •If σ0(td) = ∅,then this means that the distribution of the evolution rules in Π will not be changed anymore and only evolution rules may still be working. Hence, in that case we take σ(td) = ntd, tf do.At some point of the simulation we assume that no rule from t0 dcan be applied anymore, i.e., the computation in Π is halting. This halting condition for Π is checked by applying the table tf din GLwhere tf d= tf,1 d∪tf,2 d∪tf,3 d∪e tand tf,1 d={(a, i0)→a|a∈O, there is no rule for (a, i0) in t0 d}, tf,2 d={(X, j)→λ|X∈O, there is no rule for (X, j) in t0 d, j ∈H\ {i0}} , tf,3 d={(X, j)→#|X∈O, there is a rule for (X, j) in t0 d, j ∈H}. The tables of GLas well as σcan easily be extracted from the constructions elaborated above, hence, the proof is complete. Combining the results proved in the preceding two lemmas with Theorem 8.3 from [3] (providing the equality P sEpT 0L=P sET 0L) we immediately obtain the following theorem, i.e., a characterization of PsET0Lby P systems with antiport rules for evolution rules without catalysts, but also a normal form for this kind of P systems telling us that one membrane is already sufficient: Theorem 6 P sOP A1(anti∗) = PsOP A∗(anti∗) = PsEpT 0L=P sET0L. 6 Conclusion We have investigated P systems with antiport rules for evolution rules, where only evolution rules but no objects are moved across the membranes during a computation. We have shown that for such systems we obtain universal computational power when using purely catalytic evolution rules even with only one catalyst in one membrane. When using such systems without catalysts, a characterization of the family of languages generated 191