P Systems with Adjoining Controlled Communication Rules

P Systems with Adjoining Controlled Communication Rules Mihai Ionescu1, Drago¸s Sburlan2 1Rovira i Virgili University Research Group on Mathematical Linguistics Tarragona, Spain [email protected] 2Ovidius University Faculty of Mathematics and Informatics Constantza, Romania [email protected]o Summary. This paper proposes a new model of P systems where the rules are activated by objects present in the neighboring regions. We obtain the computational completeness considering only two membranes, external inhibitors and carriers. Leaving the carriers apart we obtain equality with ET0L systems in terms of number sets. 1 Introduction Having as inspiration the way living cells are divided by membranes into compartments where various biochemical processes take place, P systems (also known as membrane systems) area grew rapidly since Gheorghe P˘aun, proposed the first model in 1998 ([4]). A complete bibliography of P systems can be found on the P system webpage ([8]). Within the living cell there are several energy consuming activities. Among them there is the transport activity which is of three types: diffusion,facilitated diffusion, and active transport. Simple diffusion means that the molecules can pass directly through the membrane, always down a concentration gradient, while in the case of facilitated diffusion and active transport molecules can pass both down an up the concentration gradient. In the facilitated diffusion membrane protein channels are used to allow charged molecules (which otherwise could not diffuse across the cell membrane) to freely diffuse the cell, while active transport requires the expenditure of energy to transport the molecule from one side of the membrane to the other. Hence, living cells get/expel from/to their environment many substances and for this aim they have developed specific transport systems across membranes, even against a concentration gradient. Often enough this necessity of the living 200 P Systems with Adjoining Controlled Communication Rules cell to expel or attract various molecules is triggered by the presence or the absence of certain chemicals in the immediate neighboring (inner or outer) regions. Here we deal with P systems where the rules from a given region are activated precisely by the presence or the absence of certain symbols in the neighboring regions. This model has a biological counterpart and it is inspired by the chemicals that pass through the membranes of the cell, from one region to another, in the sense of polarization gradient. In this case, the electrical charge plays the role of the promoter. Before going into the definition of the new model and its computational power (Section 3) let us briefly remind the reader some basic notions and notations (Section 2). Section 4 is dedicated to the conclusions and challenges for further research. 2 Preliminaries and Definitions We assume familiarity with the basics of formal language theory (see [6]), as well as with the basics of membrane computing (see [5]). An alphabet is a finite set of symbols (letters), and a word (string) over an alphabet Σis a finite sequence of letters from Σ. We denote the empty word by λ, the length of a word wby |w|, and the number of occurrences of a symbol ain wby |w|a. The (con)catenation of two words xand yis denoted by xy. Alanguage over Σis a (possibly infinite) set of words over Σ. The language consisting of all words over Σis denoted by Σ∗, and Σ+=Σ∗\{λ}. We denote by REG,CF,ET0L,CS,RE the families of languages generated by regular, context-free, table Lindemayer interactionless systems context-sensitive, and of arbitrary grammars, respectively (RE stands for recursively enumerable languages). The following strict inclusions hold: REG ⊂CF ⊂ET0L ⊂CS ⊂RE. For a family FL of languages, NFL denotes the family of length sets of languages in FL. The following relations hold: NREG =NCF ⊂NET0L ⊂NCS ⊂NRE. The multisets over a given finite support (alphabet) are represented 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 (see [1] for other ways to specify multisets). 3 The Model Based on the biological observations mentioned in the introductory section we introduce the following new class of P systems. 3.1 Defining the Model Definition 1. A P system with adjoining controlled communication rules (called in short, a PACC system) is a construct M. Ionescu, D. Sburlan 201 Π= (V, C, µ, w1, . . . , wm, R1, . . . , Rm, i0), where: •Vis the alphabet of objects; •C⊆Vis the set of carriers; •µis a membrane structure with mmembranes (labeled in a one-to-one manner by 1, . . . , m); •w1, . . . , wmare the multisets of objects initially present in the regions of Π; •R1, . . . , Rmare finite sets of communication rules associated to membranes, that are of the following types: simple rules: Ai−→  iαor A i−→ αi, for A∈V\C,α∈(V\C)∗, promoted simple rules: AiB−→  iαor ABi−→ αi, for A, B ∈V\C,α∈(V\C)∗, inhibited simple rules: Ai¬B−→  iαor A¬Bi−→ αi, for A, B ∈V\C,α∈(V\C)∗, carrier rules: pairs of rules cAi−→  icα and c i−→ ci, for A∈V\C,c∈C, α∈(V\C)∗, or pairs of rules cA i−→ cαiand ci−→  icfor A∈V\C,c∈C, α∈(V\C)∗, promoted carrier rules: pairs of rules cAiB−→  icα and c i−→ ci, for A, B ∈V\C,c∈C, α∈(V\C)∗, or pairs of rules cABi−→ cαiand ci−→  ic, for A, B ∈V\C,c∈C, α∈(V\C)∗; inhibited carrier rules: pairs of rules cAi¬B−→  icα and c i−→ ci, for A, B ∈V\C,c∈C, α∈(V\C)∗, or pairs of rules cA¬Bi−→ cαiand ci−→  ic, for A, B ∈V\C,c∈C, α∈(V\C)∗; •i0∈ {1, . . . , m}is an elementary membrane of µ(the output membrane). In a simple rule an object is rewritten in a string of objects, in the inner or outer region with respect to the initial object. A promoted simple rule/inhibited simple rule has the same action as a simple rule but it can be applied only in the presence/absence of certain objects (chemicals) called promoters/inhibitors. To be more precise we take as example the rule AiB−→  iα, which implies that object Ais rewritten in αin the outer membrane only if promoter B is present there. If we replace Bwith ¬B, the object plays the role of the inhibitor, and only by its presence it blocks the execution of the rule. In a carrier rule the objects can be rewritten only if they are guided by an object, the carrier. Note that the carrier is not actively participating in the reaction. Its role is to “accompany” the reaction and to inhibit the parallelism. As an 202 P Systems with Adjoining Controlled Communication Rules example, by rule cAi−→  icα we mean that object Aevolves to α(in the outer region of object A) iff there is an object cthat helps Ato be rewritten. Promoted/Inhibited carrier rules can be applied if besides the carrier there is also a promoter/inhibitor which triggers/blocks the reaction. As usual in membrane computing, the rules are used in a nondeterministic maximally parallel manner starting from an initial configuration. In this way, we obtain transitions between the configurations of the system. A configuration is described by the m-tuple of the multisets of objects present in the mregions of the system. The initial configuration is (w1, . . . , wm). A sequence of transitions between configurations of the system constitutes a computation; a computation is successful if it halts, i.e., it reaches a configuration (the halting configuration) where no rule can be applied to any of the objects. The result of a successful computation is the number of objects present within the membrane with the label ioin the halting configuration. A computation which never halts yields no result. We use the notation NPACCm(α, β), where α∈ {smp} ∪ {catk|k≥0}, β∈ {proRi, inhRi}to denote the family of sets of natural numbers generated by P systems with adjoining controlled communication rules having at most m membranes, communication rules that can be simple α=smp, or carrier α=catk, using at most kcarriers, and external promoters β=proRior external inhibitors β=inhRiof weight iat the level of rules. 3.2 An Example Let us now exemplify the functioning of the model defined above throughout an example. Here it shown how such machines can be used to compute functions. Consider the following system: Π1= ({A, B, D}, C ={c},[ [ ]2]1, w1={An}, w2={c}, R1, R2,2), where: •R1=∅,R2={A 2−→ ABD2,B2−→  2B,cD2−→  2c, BD2−→ AB2,c 2−→ c2}. The system Πis fed with n≥1 copies of object Ain region 1 and when it halts, the contents of the output region contains n2copies of A. The functioning of the system is rather simple. The only rule we can apply in the initial configuration is the one which rewrites object Ain ABD in the inner region, hence in the second step of the computation we will have all the objects of the system (ncopies of A,ncopies of B,ncopies of Dand the object initially present here, carrier c) in region 2. Then, we expel all objects Bin region 1 and we start consuming objects Dby applying the rule cD2−→  2c, hence object Dis sent outside membrane 2 and is rewritten to λhaving carrier caccompanying the reaction. M. Ionescu, D. Sburlan 203 Note that object Dplays the role of the counter and each time a copy of Dis deleted (for example in step iof the computation), nmore copies of Aare produced (in step i+ 2 of the computation). One by one the n-th copies of Dare consumed, adding for each of them ncopies to object A. In the rule BD2−→ AB2, object Dplays also the role of promoter and object Bcan be rewritten into AB only in its presence. The computation ends with n2copies of Ain region 2, hence the system computes the number-theoretic function f(n) = n2,n≥1. 3.3 The Results In what follows we will prove that the class of sets of numbers generated by P systems with external inhibitors equals the class of sets of numbers generated by P systems with external inhibitors and only two membranes. Lemma 1. NPACCm(smp, inhR1) = NP ACC2(smp, inhR1), m ≥2. Proof. Obviously, NP ACCm(inh)⊇NP ACC2(inh). For the opposite inclusion we have to show that for any P system with external inhibitors Π= (V , C, µ, R, i0) generating a set of natural numbers, there exists an equivalent P system with external inhibitors Π= (V, C, µ, R, i0) with only 2 membranes. To this aim, we simulate the computation of Π, with the system Πdefined as follows. Let us denote by L={1,2, . . . , m}the set of labels of the regions in Πm. In addition, assume that R={R1, . . . , Rm}, and each Ri∈R, 1 ≤i≤m, contains all the rules that cross membrane i. Then, we define: •V={ai|a∈V , i ∈ L}; •C=C=∅; Let h:V∗× L → V∗be a mapping such that 1) h(a, i) = ai, a ∈V , i ∈ L, 2) h(λ, j) = λ,j∈ L, 3) h(x1x2, j) = h(x1, j)h(x2, j), x1, x2∈V∗,j∈ L, •denote 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i−→ αi∈Ri,A∈V,α∈V∗,i∈ L, we add to Rthe rule h(A, j)1−→ h(α0, i)1, providing that jis the label of the outer membrane of membrane i. For each rule A¬Bi−→ αi∈Ri,A, B ∈V,α∈V∗,i∈ L, we add to Rthe rule h(A, j)¬h(B, i)1−→ h(α0,2)1, providing that jis the label of the outer membrane of membrane i. For each rule Ai−→  iα∈Ri,A, B ∈V,α∈V∗,i∈ L, we add to Rthe rule h(A, i)1−→  1h(α0, j) providing that jis the outer membrane of membrane i. 204 P Systems with Adjoining Controlled Communication Rules For each rule Ai¬B−→  iα∈Ri,A, B ∈V,α∈V∗,i∈ L, we add to Rthe rule h(A, i)1¬h(B, j)−→  1h(α0, j) providing that jis the outer membrane of membrane i. Generally speaking, the purpose of membranes is to keep private the interior rules and objects from the neighboring ones and vice-versa. However, in our case we can express the passage of certain symbol through the membranes by using new symbols that we add to vocabulary and that encode both the crossed membrane label and the symbols from where they derive. In this way we can rewrite the rules, using the new symbols that perfectly describe the passage of objects in the membrane structure; consequently, in our case, we can shrink an arbitrarily membrane structure to only two membranes. The morphism used by the above construction accomplishes the encoding procedure. The system Πsimulates all the moves of Πand it stops whenever Πstops. However, in the halting configuration, in the designated output region of Π, there could be some objects representing the encoded version of the objects present in the regions of Π. Therefore, we have to modify the above set of rules such that Πeliminates all these objects in order to generate the same set of numbers as Π. This can be accomplish by producing an object Dwhenever a rule of Πis simulated (by adding the object Dat the right hand side of each above rule), deleting it at each step (we add to Rrules of type D1−→ λ1and D1−→  1λ). Finally, if Πstops, then Πwill not produce the object Danymore, hence the absence of this object can trigger an inhibited rule that deletes all the unnecessary objects. Consequently, we have that NPACCm(smp, inhR1) = NPACC2(smp, inhR1), m ≥2. Here we will prove that the family of sets of vectors of numbers generated by P systems with external inhibitors equals the family of sets of numbers generated by ET0L systems. Theorem 1. NPACC2(smp, inhR1) = NET0L. Proof. We will prove the result by showing that communicative P systems with external inhibitors are equivalent with P systems with inhibitors, which at their turn, generates the same class of sets of numbers as the Parikh image of ET0Las shown in [7]. Let NP1(smp, inhR1) be the family of sets of numbers generated by P systems with inhibitors. The proof of the inclusion NP1(smp, inhR1)⊇NPACC2(smp, inhR1) is rather simple and is based on a similar encoding of regions into new objects as was presented above. For the inclusion NP1(smp, inhR1)⊆NP ACC2(smp, inhR1) we will simulate the computation of a P system with one region Πinh = (V, C, µ, w, R, i0). We assume that the set of rules Rcontains rules of type A→αor A→α|¬B, A, B ∈V,α∈V∗. Let us consider the sets e V={e A|A∈V}and ˙ V={˙ A|A∈V}. In addition, let us define the morphisms: M. Ionescu, D. Sburlan 205 h1:V∗→e V∗, such that h1(A) = e Afor all A∈V; h2:V∗→˙ V∗, such that h3(A) = ˙ Afor all A∈V. We construct a P system Πcc = (V , C, µ, R, i0), simulating Πinh, defined as follows: V=V∪e V∪˙ V∪ {F};w1=w; C=∅;w2=w; µ=21;i0= 1. The set of rules Ris defined as follows3: step i A¬B−→ h1(α)h2(α),for all rules A→α|¬B∈Rinh, step i A −→ h1(α)h2(α),for all rules A→α∈Rinh, step iA−→  F, if exists A→α∈Rinh, step iA¬B−→  F, if exists A→α|¬B∈Rinh, step i+ 1 F −→  , step i+ 1 h1(A)−→  h1(A),for all objects A∈V, step i+ 2 h1(A) −→ A,for all objects A∈V, step i+ 2 h2(A)¬R−→  A, for all A∈V. Here is how the system Πcc simulates the computation of Πinh. First, remark that in order to correctly simulate the moves of Πinh, we will maintain during the computation in both regions of Πcc a copy of the multiset w– the multiset that represent the current configuration of Πinh. This is especially useful when trying to simulate rules of type A→α|¬B∈Rinh because we have to know whether or not the external inhibitor is present. We assume that the system is in a configuration given by the strings w1= w2=w. The system attempts to execute simultaneously the rules of type step i A¬B−→ h1(α)h2(α),for all rules A→α|¬B∈Rinh, step i A −→ h1(α)h2(α),for all rules A→α∈Rinh, step iA−→  F, if exists A→α∈Rinh, step iA¬B−→  F, if exists A→α|¬B∈Rinh. Remark that the rules of first two types are used to generate inside the inner region, two copies of multiset α(represented by h1(α) and h2(α)). In the same 3For the present proof, we will simplify the notation by not including the membrane labels into the syntax of the rules; this is possible here since we have only two membranes and we do not allow the interaction with the environment. In addition, we have specified on their left hand side the moment of their executions during the simulation of one computational step in Πinh. 206 P Systems with Adjoining Controlled Communication Rules time, the rules of second type delete from region 2 the objects that were within the scope of rules of first type. In addition, remark that there are no other rules that can be applied in this step. Moreover, they produce in region 1 objects R; these objects will be used later for synchronizing the moments when multiset α appears in both regions. Next, are executed the rules of type: step i+ 1 F −→  , step i+ 1 h1(A)−→  h1(A),for all objects A∈V. Observe that the presence of object(s) Rin this computational step inhibits the executions of rules of type h2(A)¬F−→  A, for all A∈V. Hence, in the third step, the rules of type h1(A) −→ A,for all objects A∈V, h2(A)¬F−→  A, for all A∈V, will be executed. The new objects appear at the same time in both regions of the system Πcc and the simulation of the next computational step of Πinh can start. Finally, if the system Πinh stops because there are no rules to be applied, then also Πcc halts. Before we conclude, remark that the maximal parallelism as well as the universal clock is fundamental for the construction. Consequently we have proved that the computation of an arbitrary P system with inhibitors can be simulated by a P system with external inhibitors, hence we have NP1(smp, inhR1)⊆NP ACC2(smp, inhR1). Therefore we have that NP1(smp, inhR1) = NPACC2(smp, inhR1) = P sET0L. The following theorem shows that P systems with external inhibitors and carriers are computationally complete. Theorem 2. NP ACC2(cat, inhR1) = NRE. Proof. The inclusion NP ACC2(cat, inhR1)⊆NRE is assumed true by invoking the Turing-Church thesis. For the inclusion NPACC2(cat, inhR1)⊇NRE we will simulate the computation of an arbitrary non-deterministic register machine M= (n, P, l0, lh). Such register machines are computational universal if n≥3. We construct Π= (V, C, µ, w1, w2, R1, i0) as follows. V={ai, Ai, Si|1≤i≤n}∪{l, l, l,e l,e e l, L |l∈Lab(P)}∪{c} ∪ {K, K, K, K, T0, T1, X, X}; C={c}; µ=21; M. Ionescu, D. Sburlan 207 w1=l0L0ak1 1. . . akn nc; w2=A1. . . AnS1. . . Sn; i0= 1. The set of rules Ris defined as follows: •for each instruction (l1: ADD(j), l2, l3)∈ P, the set Rcontains the rules: l1  −→ A1. . . Aj−1Aj+1 . . . AnS1. . . Snajl2,l16=lh, l1  −→ A1. . . Aj−1Aj+1 . . . AnS1. . . Snajl3,l16=lh, L1¬Aj−→ A1. . . AnS1. . . Sn, l2−→  l2, l3−→  l3, aj−→  aj, Ai−→  λ, 1 ≤i≤n, Si−→  λ, 1 ≤i≤n; •for each instruction (l1: SUB(r), l2, l3)∈ P, the set Rcontains the rules: l1  −→ A1. . . AnS1. . . Sj−1Sj+1 . . . Snl1,l16=lh, caj¬Sj−→ A1. . . AnS1. . . SnX, L1¬Sj−→ A1. . . AnS1. . . SnK, l1−→  l1, X−→  X, l1  −→ l1T0A1. . . AnS1. . . Sn, K−→  K, l1¬X−→  e l3, X¬T0−→ l2, K  −→ A1. . . AnS1. . . SnK, T0−→  T1, l1¬K−→  λ, l2−→  l2L2, T1  −→ A1. . . AnS1. . . Sn, e l3  −→ e e l3, e e l3−→  l3L3, K−→  K,