On the Power of Insertion P Systems of Small Size

On the Power of Insertion P Systems of Small Size Alexander Krassovitskiy Research Group on Mathematical Linguistics, Rovira i Virgili University Av. Catalunya, 35, Tarragona 43002, Spain [email protected] Summary. In this article we investigate insertion systems of small size in the framework of P systems. We consider P systems with insertion rules having one symbol context and we show that they have the computational power of matrix grammars. If contexts of length two are permitted, then any recursively enumerable language can be generated. In both cases an inverse morphism and a weak coding were applied to the output of the corresponding P systems. 1 Introduction The study of insertion-deletion operations on strings has a long history. We just mention [18], [5], [7], [13], [15]. Motivated from molecular computing they have been studied in [1], [6], [17], [19], [12]. With some linguistic motivation they may be found in [11] and [3]. In general form, an insertion operation means adding a substring to a given string in a specified (left and right) context, while a deletion operation means removing a substring of a given string from a specified (left and right) context. A finite set of insertion/deletion rules, together with a set of axioms provide a language generating device: starting from the set of initial strings and iterating insertion-deletion operations as defined by the given rules we get a language. The number of axioms, the length of the inserted or deleted strings, as well as the length of the contexts where these operations take place are natural descriptional complexity measures of the insertion-deletion systems. Some combinations of parameters lead to systems which are not computationally complete [14], [8] or even decidable [20]. It was shown that the operations of insertion and deletion considered in P systems framework can easily increase the computational power with respect to ordinary insertion-deletion systems [9], [10]. Traditionally, language generating devices having only insertion rules were studied. Early computational models based only on insertion appear already in [11], and are discussed in [17] and [16] (with membrane tree structure). It was 30 A. Krassovitskiy proved that pure insertion systems having one letter context are always contextfree. Yet, there are insertion systems with two letter context which generate nonsemilinear languages (see Theorem 6.5 in [17]). On the other hand, it appears that by using only insertion operation the obtained language classes with context greater than one are incomparable with many known language classes. For example there is a simple linear language {anban|n≥1}which cannot be generated by any insertion system (see Theorem 6.6 in [17]). In order to overcome this obstacle one can use some codings to “interpret” generated strings. In [17], in a natural way, there were used two additional string operations: a morphism hand a weak coding ϕ. The result is considered as a product of application h−1◦ϕon the generated strings. Clearly, the obtained languages have greater expressivity and the corresponding language class is more powerful. It appears that with the help of morphisms and codings one can obtain every RE language if insertion rules have sufficiently large context. It is proved in [17] that for every recursively enumerable language Lthere exists a morphism h, a weak coding ϕand a language L0generated by an insertion system with rules using the length of the contexts at most 7, such that, L=h(ϕ−1(L0)).The result was improved in [2], showing that rules having at most 5 letter context are sufficient to encode every recursively enumerable language. Recently, in [4] it was shown that the same result can be obtained with the length of contexts equal to 3. In this article we consider the encoding as a part of insertion P systems. The obtained model is quite powerful and has the power of matrix languages if contexts of length one are used. We also show that if no encoding is used, then the corresponding family is strictly included in MAT and equals CF if no membranes are used. If an insertion of two symbols in two letters contexts is used, then all recursively enumerable languages can be generated (of course, using the inverse morphism and the weak coding). 2 Prerequisites All formal language notions and notations we use here are elementary and standard. The reader can consult any of the many monographs in this area (see details, e.g., in [18]). We denote by |w|the length of a word wand by card(A) the cardinality of the set A, and εdenotes the empty string. An insertion-deletion system is a construct ID = (V, T, A, I, D),where Vis an alphabet, T⊆V,Ais a finite language over V, and I, D are finite sets of triples of the form (u, α, v), where u,α, and vare strings over V. The elements of T are terminal letters (in contrast, those of V\Tare called nonterminals), those of Aare axioms, the triples in Iare insertion rules, and those from Dare deletion rules. An insertion rule (u, α, v)∈Iindicates that the string αcan be inserted in between uand v, while a deletion rule (u, α, v)∈Dindicates that αcan be On the Power of Insertion P Systems of Small Size 31 removed from the context (u, v). As stated otherwise, (u, α, v)∈Icorresponds to the rewriting rule uv →uαv, and (u, α, v)∈Dcorresponds to the rewriting rule uαv →uv. We denote by =⇒ins the relation defined by an insertion rule (formally, x=⇒ins yiff x=x1uvx2, y =x1uαvx2, for some (u, α, v)∈Iand x1, x2∈V∗) and by =⇒del the relation defined by a deletion rule (formally, x=⇒del yiff x=x1uαvx2, y =x1uvx2, for some (u, α, v)∈Dand x1, x2∈V∗). We refer by =⇒to any of the relations =⇒ins,=⇒del, and denote by =⇒∗the reflexive and transitive closure of =⇒(as usual, =⇒+is its transitive closure). The language generated by ID is defined by L(ID) = {w∈T∗|x=⇒∗w, x ∈A}. A (pure) insertion systems of weight (n, m, m0) is a construct ID = (V, A, I), where Vis a finite alphabet, I⊆V∗is a finite set of axioms, Iis a finite set of insertion rules of the form (u, α, v),for u, α, v ∈V∗, and n= max{|α| | (u, α, v)∈I}, m= max{|u| | (u, α, v)∈I}, m0= max{|v| | (u, α, v)∈I}. We denote by INSm,m0 ncorresponding families of languages generated by insertion systems. An insertion P system is the following construct: Π= (V, µ, M1, . . . , Mk, R1, . . . , Rk), where •Vis a finite alphabet, •µis the membrane (tree) structure of the system which has nmembranes (nodes). This structure will be represented by a word containing correctly nested marked parentheses. •Mi,for each 1 ≤i≤k, is a finite language associated to the membrane i. •Ri,for each 1 ≤i≤k, is a set of insertion rules with target indicators associated to membrane iand which have the following form: (u, x, v;tar), where (u, x, v) is an insertion rule, and tar, called the target indicator, is from the set {here, inj, out},1≤j≤k. Any k-tuple (N1, . . . , Nk) of languages over Vis called a configuration of Π. For two configurations (N1, . . . , Nk) and (N0 1, . . . , N0 k) of Πwe write (N1, . . . , Nk) =⇒(N0 1, . . . , N0 k) if we can pass from (N1, . . . , Nk) to (N0 1, . . . , N0 k) by applying nondeterministically the insertion rules, to all possible strings from the corresponding regions, and following the target indications associated with the rules. We assume that every string represented in a membrane has arbitrary many copies. Hence, by applying a rule to a string we get both arbitrary many copies of resulted string as well as old copies of the same string. More specifically, if w∈Ni 32 A. Krassovitskiy and r= (u, x, v;tar)∈Ri, such that w=⇒rw0then w0will go to the region indicated by tar. If tar =here, then the string remains in Ni, if tar =out, then the string is moved to the region immediately outside the membrane i(maybe, in this way the string leaves the system), if tar =inj, then the string is moved to the region j. A sequence of transitions between configurations of a given insertion P system Π, starting from the initial configuration (M1, . . . , Mn), is called a computation with respect to Π. The result of a computation consists of all strings over Vwhich are sent out of the system at any time during the computation. We denote by L(Π) the language of all strings of this type. We say that L(Π) is generated by Π. The insertion-deletion tissue P systems are defined in an analogous manner. As the tissue P systems use arbitrary graph structure we write the target indicator in the form tar =goj, j = 1, . . . , k. The result of a computation consists of all strings over Vwhich are sent to one selected output cell. The weight of insertion rules (n, m, m0) and the membrane degree kdescribe the complexity of an insertion P system. We denote by LSPk(insm,m0 n) (see, for example [16]) the family of languages L(Π) generated by insertion P systems of degree at most k≥1 having the weight at most (n, m, m0). If some of the parameters n, m, m0,or kis not specified we write “ * ” instead. We say that a language L0is from hINSm,m0 n(from hLSPk(insm,m0 n), correspondingly) if there exist a morphism h, weak coding ϕand L(Π)∈INSm,m0 n (L(Π)∈LSPk(insm,m0 n) such that ϕ(h−1(L(Π))) = L0. We write an instance of the system hLSP in the form (V, µ, M1, . . . , Mn, R1, . . . , Rn, h, ϕ), where •his a morphism h:V→V+, •ϕis a weak coding ϕ:T→T∪ {ε}, •other components are defined as for insertion P system. We insert “t” before P to denote classes corresponding to the tissue cases (e.g., hLStP). Insertion (t) holds for both tissue and tree membrane structure. We say that a letter ais marked in a sentential form waw0if it is followed by #,i.e., |w0|>0, and # is the prefix of w0.In the following proofs we use a marking technique introduced in [16]. The technique works as follow: in order to simulate rewriting production A→Bwe add adjacently right from Athe word #Bspecifying that letter Ais already rewritten. And, as soon as the derivation is completed, every pair A# in the sentential form is subject to the inverse morphism. On the Power of Insertion P Systems of Small Size 33 3 Main Results Let us consider insertion systems (without membranes) with one letter context rules hINS1,1 ∗. Applying the marking technique we get a characterization of context-free languages. Theorem 1 hINS1,1 ∗=CF Proof. First we show that CF ⊆hINS1,1 3. Let G= (V, T, S, P) be a context-free grammar in Chomsky normal form. Consider the following system from hINS1,1 3 Π= (T∪V∪ {#}, R, {S}, h, ϕ), where R={(A, #BC, α)|α∈T∪V, A →BC ∈P},the morphism h h(a) = a#,if a∈V, and h(a) = a, if a∈T, and the weak coding ϕ ϕ(a)→ε, if a∈V, ϕ(a)→a, if a∈T. We claim that L(Π) = L(G).Indeed, each rule (A, #BC, α)∈Rcan be applied in the sentential form wAαw0if Ais unmarked (not rewritten). Thus, the production A→BC ∈Pcan be applied in the corresponding derivation G. Hence, by applying the counterpart rules we get equivalent derivations. At the end of derivation, by applying the inverse morphism h−1we warranty that every nonterminal is marked. Finally, we delete every nonterminal by the weak coding ϕ. Hence L(Π) = L(G),and we get CF ⊆hINS1,1 3. The equivalence of the two classes follows from Theorem 6.4 in [17] stating INS1,1 ∗⊆CF and the fact that context-free languages are closed under inverse morphisms and weak codings. Now we consider insertion systems with contexts controlled by membranes (P systems). It is known from Theorem 5.5.1 in [16] that LSP2(ins1,1 2) contains non context-free languages. We show that this class is bounded by matrix grammars: Lemma 2 LStP∗(ins1,1 ∗)⊂MAT. Proof. The proof uses the similar technique presented in [17], Theorem 6.4 for context-free grammars. Let Π= (V, µ, M1, . . . , Mn, R1, . . . , Rn) be a system from LStPn(ins1,1 ∗) for some n≥1. Consider a matrix grammar G= (D∪Q∪ {S}, V, S, P ),where Q={Qi|i= 1, . . . , n},D={Da,b |a, b ∈V∪ {ε}}, and Pis constructed as follows: 34 A. Krassovitskiy 1. For every rule (a, b1. . . bk, c, goj)∈Ri, a, b1, . . . , bk, c ∈V∪ {ε}, k > 0 we add to P(Qi→Qj, Da,c →Da,b1Db1,b2. . . Dbk−1,bkDbk,c),where a=½a, if a∈V, t, ∀t∈V∪ {ε},if a=εc=½c, if c∈V, t, ∀t∈V∪ {ε},if c=ε 2. For every rule (a, ε, c, inj)∈Ri, a, c ∈V∪ {ε}, k > 0 we add to P (Qi→Qj, Da,c →Da,c),where aand cdefined as in the previous case. 3. Next, for every w=b1· · ·k∈Mi, i = 1, . . . , n, k > 0 we add to Pthe matrix (S→QiDε,b1Db1,b2. . . Dbk−1,bkDbk,ε). 4. In special case if ε∈Miwe add (S→QiDε,ε) to P. 5. Also, for every Da,b ∈D, a, b ∈V∪ {ε}we add (Da,b →a) to P. 6. Finally, we add (p1→ε) to P(we assume that the first cell is the output cell). The simulation of Πby the matrix grammar is straightforward. We store the label of current cell by nonterminals Q. Every nonterminal Da,c ∈D, a, c ∈V∪{ε}, represents a pair of adjacent letters, so we can use them as a context. A rule (a, b1. . . bk, c, inj)∈Ri, a, c ∈V, b1. . . bk∈Vk, can be simulated by the grammar iff the sentential form contains both Qiand Da,c.It results the label of current cell is rewritten to Qjand Da,c is rewritten to the string Da,b1Db1,b2. . . Dbk−1,bkDbk,a. Clearly, the string preserves one symbol context. In order to treat those rules which have no context we introduce productions that preserve arbitrary context (a∈V∪ {ε}and c∈V∪ {ε}). The simulation of the grammar starts with a nondeterministic choice of the axiom. Then, during the derivation any rule corresponding to the context (a, b) have to be applied (in a one to one correspondence with grammar productions). Finally, the string over Vis produced by the grammar iff Q1has been deleted from the simulated sentential form. The deletion of Q1specifies that Πreached the output cell. So, we obtain L(Π) = L(G). Hence, LStP∗(ins1,1 ∗)⊆MAT. The strictness of the inclusion follows from the fact there are languages from MAT which cannot be generated by any insertion P system from LStP∗(ins1,1 n),for any n≥1.Indeed, consider La={cakcakc|k≥1}.One may see that the matrix grammar ({Sl, Sr, S},{a, b}, S, P 0) generates La,where P0={(S→cSlcSrc), (Sl→ε, Sr→ε), (Sl→aSl, Sr→aSr)}. On the other hand, La/∈LStP∗(ins1,1 n),for any n≥1.For the contrary, assume there is such a system. We note that the system cannot delete or rewrite any letter so every insertion is terminal. And, as the language of axioms is finite, we need an insertion rule of letter a. Consider alternatives for a final insertion step in a derivation which has at most one step and derives a word cakcakc, for some k > n: (1) the last applied rule inserts the central letter c, or (2) it does not insert the On the Power of Insertion P Systems of Small Size 35 central letter c. (1) The central ccan be inserted between any two letters a. So we get a contradiction because the prefix capcmay not be equal to the suffix caqc. (2) The last applied rule can (2.1) either insert the letter c(at the end or start of the string) or, (2.2) no cis inserted by the final rule. (2.1) We get a contradiction because ccan be alternatively inserted in between two aas we assumed k > n. (2.2) The last rule cannot distinguish whether to insert abefore the central cor after the central c. So, again, we get a contradiction because the prefix capcmay not be equal to the suffix caqc. So we proved La/∈LStP∗(ins1,1 n),for any n≥1 and hence LStP∗(ins1,1 ∗)⊂MAT. Corollary 3 LSP∗(ins1,1 ∗)⊂MAT. Proof. A tree is a special case of a graph. Lemma 4 MAT ⊆hLSP∗(ins1,1 2). Proof. We prove the theorem by a direct simulation of a matrix grammar G= (N, T, S, P). We assume that Gis in binary normal form, i.e., every matrix has the form i: (A→BC, A0→B0C0)∈P, where A, A0∈N, B, B0, C, C0∈ N∪T∪ {ε}and i= 1, . . . , n. Consider a system Π∈hLSPn+3(ins1,1 2), Π= (V, [1[2[3 Y i=1,...,n [i+3 ]i+3  ]3]2]1,{S$},∅, . . . , ∅, R1, . . . , Rn+3, h, ϕ), where V=N∪T∪ {Ci, C0 i|i= 1, . . . , n}∪{#,$}. For every matrix i: (A→BC, A0→B0C0) we add r.1.1 : (A, #Ci, α, in2),to R1; r.2.1 : (Ci, BC, α, in3), r.2.2 : (C0 i,#, α, out) to R2; r.3.1 : (Ci,#, α, ini+3), r.3.2 : (C0 i, B0C0, α, out) to R3; r.i + 3.1 : (A0,#C0 i, α, out),to Ri+3 for every α∈V\{#}.In addition we add (ε, $, ε, out) to R1. We also define the morphism hand the weak coding ϕby: h(a) = ½a, if a∈T, a# if a∈V ϕ(a) = ½a, if a∈T, εif a∈V∪ {$}. We claim that L(Π) = L(G).To do so it is enough to prove that w∈L(G) iff w0∈L(Π) and w0=ϕ(h−1(w)). 36 A. Krassovitskiy First we show that for every w∈L(G) there exists w0∈L(Π) and w0=ϕ(h−1(w)).Consider the simulation of the i-th matrix (A→BC, A0→B0C0)∈P. The simulation is controlled by letters Ciand C0 i. First, we insert #Ciin the context of a unmarked Aand send the obtained string to the second membrane. Then we use Cias a context to insert adjacently right the word BC. After that, we mark the control letter Ciand send the sentential form to the i+ 3 membrane. Here we choose nondeterministically one letter A0, mark it, write adjacently right new control letter C0 i, and, after that, send the obtained string to the third membrane. We mention that it is not possible to apply the rule r.i + 3.1 : (A0,#C0 i, α;out)ein the i+ 3 membrane and to reach the skin membrane if the sentential form does not contain the unmarked A0. So, this branch of computation cannot influence the result and may be omitted in the consideration. Next, in the third membrane, B0C0is inserted in the context of unmarked C0 iand the sentential form is sent to the second membrane. Finally, we mark C0 iand send the resulting string back to the skin membrane. We assume that at the beginning of this simulation the sentential form in the skin membrane does not contain unmarked Ci, C0 i.Hence, the insertions in the second and third membranes are deterministic. The derivation preserves the assumption, as after the sentential form is sent back to the skin membrane the introduced Ci, and C0 iare marked. At the end of computation we send the obtained sentential form out of the system by the rule (ε, $, ε, out). Let wbe a string in the skin region which contains some unmarked Aand A0. If the letter Aprecedes B, then we can write w=w1Aα1w2A0α1w3.The simulation of the matrix is the following w1Aα1w2A0α1w3 r.1.1,r.2.1,r.3.1 =⇒w1A#Ci#BCα1w2A0α1w3 r.3+i.1,r.3.2,r.2.2 =⇒ w1A#Ci#BCα1w2A0#C0 i#B0C0α1w3, where w1, w2, w3∈V∗, α1, α2∈V\{#}.We can write the derivation similarly if Bprecedes A. Hence, as a result of the simulation of i-th matrix we get both Aand A0 marked and BC,B0C0inserted in the right positions. The derivation in Πmay terminate by the rule (ε, $, ε, out) only in the first membrane. This guarantees that the simulation of each matrix has been finished. According to the definition of Π the string w0belongs to the language if w0=ϕ(h−1(w)),where wis the generated string. This is the case only if the resulting output of Πdoes not contain unmarked nonterminals. Hence we proved L(G)⊆ϕ(h−1(L(Π))). The inverse inclusion is obvious since every rule in Πhas its counterpart in G. The case when the derivation in Πis blocked corresponds to the case a matrix cannot be finished. Hence, we get MAT ⊆hLSP∗(ins1,1 2). Remark 5 One can mention that a similar result can be obtained with a smaller number of membranes at the cost of increasing the maximal length of inserted On the Power of Insertion P Systems of Small Size 37 words. I.e., for any grammar G0from MAT there is a P insertion system Π0 corresponding to hLSPn+1(ins1,1 3)such that L(G) = L(Π0),and nis the number of matrices in G0.To prove this we can use the same argument as in the previous theorem and replace rules (r. ∗.∗) by (A, #BC, α, ini+1), α ∈V\{#}to R1 (A0,#B0C0, α, in1), α ∈V\{#}to Ri+1. Corollary 6 MAT ⊆hLStP∗(ins1,1 2). Proof. Obvious, since a tree is a special case of a graph. Taking into account Lemma 4, Lemma 2, and the fact that the class of matrix grammars is closed under inverse morphisms and weak codings we get the following characterization of MAT: Theorem 7 hLS(t)P∗(ins1,1 ∗) = MAT. Next we consider computationally complete insertion P systems. In order to use concise representations of productions in 0-type grammars we need an auxiliary lemma. Lemma 8 For every 0-type grammar G0= (N0, T, S0, P 0)there exists a grammar G= (N, T, S, P)such that L(G) = L(G0)and every production in Phas the form AB →AC or AB →CB or (1) A→AC or A→CA or (2) A→δ, (3) where A, B and Care from Nand δ∈T∪N∪ {ε}. Proof. To prove the lemma it is enough to show that for any grammar in Penttonnen normal form there is an equivalent grammar having productions of the form (1)–(3). To do so it is enough to simulate the context-free productions A→BC by productions of the form (1)–(3). Let G= (N, T, S, P) be a grammar in Penttonnen normal form whose production rules in Pare of the form: AB →AC or A→BC or A→α where A, B, C and Dare from Nand α∈T∪N∪ {ε}. Let PCF ⊆Pdenotes the set of all context-free productions A→BC ∈P such that B6=C. Suppose that rules in PCF are ordered and n=card(PCF ). Consider a grammar G0= (N0, T, S, P 0),where N0=N∪ {Xi, Yi, Zi|i= 1, . . . , n}, P0= (P\PCF )∪P0 CF ,and P0 CF is constructed as follows: for every i:A→BC ∈PCF add to P0 CF the following productions