P Systems with Minimal Insertion and Deletion

P Systems with Minimal Insertion and Deletion Artiom Alhazov1,3, Alexander Krassovitskiy2, Yurii Rogozhin2,3, Sergey Verlan4 1IEC, Department of Information Engineering, Graduate School of Engineering Hiroshima University, Higashi-Hiroshima 739-8527 Japan 2Research Group on Mathematical Linguistics, Rovira i Virgili University Av. Catalunya, 35, Tarragona 43002 Spain [email protected] 3Institute of Mathematics and Computer Science, Academy of Sciences of Moldova Academiei 5, Chi¸sin˘au MD-2028 Moldova {artiom,rogozhin}@math.md 4LACL, D´epartement Informatique, Universit´e Paris 12 61 av. G´en´eral de Gaulle, 94010 Cr´eteil, France [email protected] Summary. In this paper we consider insertion-deletion P systems with priority of deletion over the insertion. We show that such systems with one symbol context-free insertion and deletion rules are able to generate P sRE. If one-symbol one-sided context is added to insertion or deletion rules but no priority is considered, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important and in its absence the corresponding class of P systems is strictly included in MAT . 1 Introduction The operations of insertion and deletion are fundamental in formal language theory, and generative mechanisms based on them were considered (with linguistic motivation) for some time, see [14] and [6]. Related formal language investigations can be found in several places; we mention only [8], [10], [16], [19]. In the last years, the study of these operations has received a new motivation from molecular computing, see [3], [9], [21], [23], [15]. 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 10 A. Alhazov et al. length of the contexts where these operations take place are natural descriptional complexity measures in this framework. As expected, insertion and deletion operations with context dependence are very powerful, leading to characterizations of recursively enumerable languages. Most of the papers mentioned above contain such results, in many cases improving the complexity of insertion-deletion systems previously available in the literature. Some combinations of parameters lead to systems which are not computationally complete [17], [11] or even decidable [24]. However, if these systems are combined with the distributed computing framework of P systems [20], then their computational power may strictly increase, see [12], [13]. In this paper we study P systems with insertion and deletion rules of one symbol without context. We show that this family is strictly included in MAT, however some non-context-free languages may be generated. If Parikh vectors are considered, then the corresponding family equals to P sMAT . When a priority of deletion over insertion is introduced, PsRE can be characterized, but in terms of language generation such systems cannot generate a lot of languages because there is no control on the position of an inserted symbol. If one-sided contextual insertion or deletion rules are used, then this can be controlled and all recursively enumerable languages can be generated. The same result holds if a context-free deletion of two symbols is allowed. 2 Definitions 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 – for instance, [22] – for the unexplained details. We denote by |w|the length of a word wand by |w|athe number of occurrences of symbol ain w. For a word w∈V∗we denote by ∆(w) all words w0having the same number of letters as w,∆(w) = {w0|,|w0|a=|w|afor all a∈V}and we denote by t⊥ the binary shuffle operation. By card(V) we denote the cardinality of the set V. An InsDel 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), α6=λ, where uand vare strings over Vand λdenotes the empty string. The elements of Tare terminal symbols (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 removed from the context (u, v). As stated otherwise, (u, α, v)∈I corresponds to the rewriting rule uv →uαv, and (u, α, v)∈Dcorresponds to the rewriting rule uαv →uv. We refer by =⇒to the relation defined by an insertion or deletion rule. The language L(ID) generated by ID is defined as {w∈T∗|A3x=⇒∗w}. P Systems with Minimal Insertion and Deletion 11 The complexity of an InsDel system ID = (V, T, A, I, D) is described by the vector (n, m, m0;p, q, q0) called size, where n= max{|α| | (u, α, v)∈I}, p = max{|α| | (u, α, v)∈D}, m= max{|u| | (u, α, v)∈I}, q = max{|u| | (u, α, v)∈D}, m0= max{|v| | (u, α, v)∈I}, q0= max{|v| | (u, α, v)∈D}. We also denote by INSm,m0 nDELq,q0 pcorresponding families of languages. Traditionally, in the literature, instead of pairs m/m0and q/q0the maximum of both numbers is used. However, such a complexity measure is not accurate and it cannot distinguish between universality and non-universality cases, see [24] and [11]. If some of the parameters n, m, m0, p, q, q0is not specified, then we write symbol ∗ instead. For example, INS0,0 ∗DEL0,0 ∗denotes the family of languages generated by context-free InsDel systems. InsDel systems of a “sufficiently large” size characterize RE, the family of recursively enumerable languages. Now we present a definition of insertion-deletion P systems. The insertiondeletion tissue P systems are defined in an analogous manner. An insertion-deletion P system is a construct Π= (O, T, µ, M1,· · · , Mn, R1,· · · , Rn), where •Ois a finite alphabet, •T⊆Ois the terminal alphabet, •µis the membrane (tree) structure of the system which has nmembranes (nodes) and it can be represented by a word over the alphabet of correctly nested marked parentheses, •Mi,for each 1 ≤i≤n, is a finite language associated to the membrane i, •Ri,for each 1 ≤i≤n, is a set of insertion and deletion rules with target indicators associated to region i, of the following forms: (u, x, v;tar)a, where (u, x, v) is an insertion rule, and (u, x, v;tar)e, where (u, x, v) is a deletion rule, and the target indicator tar is from the set {here, inj, out |1≤j≤n}. An n-tuple (N1,· · · , Nn) of finite languages over Ois called a configuration of Π. The transition between the configurations consists in applying the insertion and deletion rules in parallel to all possible strings, non-deterministically, and following the target indications associated with the rules. A sequence of transitions between configurations of a given insertion-deletion P system Πstarting from the initial configuration is called a computation with respect to Π. We say that Πgenerates L(Π), the result of its computations. It consists of all strings over Tever sent out of the system during its computations. We denote by ELSPk(insm,m0 p, delq,q0 p) the family of languages L(Π) generated by insertion-deletion P systems with at most k≥1 membranes and insertion and deletion rules of size at most (n, m, m0;p, q, q0). We omit the letter Eif T= O. In this paper we also consider insertion-deletion P systems where deletion rules have a priority over insertion rules; the corresponding class is denoted as 12 A. Alhazov et al. (E)LSPk(insm,m0 p< delq,q0 p). Letter ”t” is inserted before P to denote classes for the tissue case, e.g., ELStPk(insm,m0 p, delq,q0 p). Aregister machine (introduced in [18], see also [4]) is a construct M= (d, Q, q0, h, P ), where •dis the number of registers, •Qis a finite set of bijective labels of instructions of P, •q0∈Qis the initial label, •h∈Qis the halting label, and •Pis the set of instructions of the following forms: 1. p: (ADD(k), q, s), with p, q, s ∈Q, 1 ≤k≤d(“increment” -instruction). Add 1 to register kand go to one of the instructions with labels q, s. 2. p: (SUB(k), q, s), with p, q, s ∈Q, 1 ≤k≤d(“decrement” -instruction). Subtract 1 from the positive value of register kand go to the instruction with label q, otherwise (if it is zero) go to the instruction with label s. 3. h:HALT (the halt instruction). Stop the computation of the machine. For generating languages over T, we use the model of a register machine with output tape (introduced in [18], see also [1]), which also uses a tape operation: 4. p: (WRITE(A), q), with p, q ∈Q,A∈T. The configuration of a register machine is (q, n1,· · · , nd), where q∈Q,ni≥0, 1≤i≤d. A register machine generates an m-dimensional vector as follows: let the first mregisters be output registers, and the computation starts from (q0,0,· · · ,0); if the configuration (h, n1,··· , nd) is reached, then the resulting vector is (n1,· · · , nm). Without restricting generality we assume (nm+1,· · · , nd) = (0,· · · ,0). The set of all vectors generated in this way by Mis denoted by Ps(M). It is known (e.g., see [18], [25]) that register machines generate P sRE. If the WRITE instruction is used, then RE can be generated. In the case when a register machine cannot check whether a register is empty we say that it is partially blind; the second type of instructions is then written as p: (SUB(k), q) and the transition is undefined if register kis zero. The word “partially” stands for an implicit test for zero at the end of a (successful) computation: counters m+ 1,· · · , d should be empty. It is known, [4], that partially blind register machines generate exactly P sMAT (Parikh sets of languages of matrix grammars without appearance checking). 3 Minimal Context-free Insertion-Deletion P Systems It has been shown, [24], that systems in INS0,0 1DEL0,0 ∗only generate strings obtained by inserting any number of specific symbols anywhere in words of a finite language; this is included in the regular languages family; strictly as, e.g., for P Systems with Minimal Insertion and Deletion 13 L={a∗b∗}the system has no control on the place of insertion or deletion in the string and the initial language is finite. Therefore, INS0,0 1DEL0,0 1⊂REG. When a membrane structure is added to minimal insertion-deletion systems without context, their computational power is increased. Theorem 1. PsStP∗(ins0,0 1, del0,0 1) = PsMAT. Proof. It is not difficult to see that dropping the requirement of the uniqueness of the instructions with the same label, the power of partially blind register machines does not change, see, e.g., [4]. We use this fact for the proof. The inclusion PsStP∗(ins0,0 1, del0,0 1)⊆PsMAT follows from the simulation of minimal context-free insertion-deletion P systems by partially blind register machines, which are known to characterize P sMAT [4]. Indeed, any rule (λ, a, λ;q)a∈Rpis simulated by instructions p: (ADD(a), q). Similarly, rule (λ, a, λ;q)e∈Rpis simulated by instructions p: (SUB(a), q). The output region i0is associated to the final state, while the halting is represented by absence of the corresponding symbols (final zero-test) as follows. We assume that Ri0has no insertion rules (∅can be generated by a trivial partially blind register machine), and the output registers correspond to those symbols that cannot be deleted by rules from Ri0. The converse inclusion follows from the simulation of partially blind register machines by P systems. Indeed, with every instruction pof the register machine we associate a cell. Instruction p: (ADD(Ak), q) is simulated by rule (λ, Ak, λ;q)a∈ Rp, and instruction p: (SUB(Ak), q) by (λ, Ak, λ;q)e∈Rp. Final zero-tests: rules (λ, Ak, λ; #)e∈Rh,k≥m, should be inapplicable (R#=∅). As the membrane structure is a tree, one-way inclusion follows. Corollary 1. PsSP∗(ins0,0 1, del0,0 1)⊆P sMAT . In terms of the generated language the above systems are not too powerful, even with priorities. Like in the case of insertion-deletion systems there is no control on the position of insertion. Hence, the language L={a∗b∗}cannot be generated, for insertion strings of any size. Hence we obtain: Theorem 2. REG\LStP∗(ins0,0 n< del0,0 1)6=∅, for any n > 0. However, there are non-context-free languages that can be generated by such P systems (even without priorities and deletion). Theorem 3. LStP∗(ins0,0 1, del0,0 0)\CF 6=∅. Proof. It is easy to see that the language {w∈ {a, b, c}∗:|w|a=|w|b=|w|c}is generated by such a system with 3 nodes, inserting consecutively a,band c. For the tree case the language {w∈ {a, b}∗| |w|a=|w|b}can be generated in a similar manner. We show a more general inclusion: 14 A. Alhazov et al. Theorem 4. ELStP∗(ins0,0 n, del0,0 1)⊂MAT , for any n > 0. Proof. As in [11] we can suppose that there are no deletions of terminal symbols. We also suppose that there is only one initial string in the system, because there is no interaction between different evolving strings and the result matches the union of results for the systems with only one string. Consider a tissue P system Πwith alphabet O, terminal symbols T, the set Hof unique cell labels and the initial string win cell labeled p0. Such a system can be simulated by the following matrix grammar G= (O∪H, T, S, P). For insertion instruction (λ, a1· · · an, λ;q)ain cell p, the matrix (p→q, D → Da1D···DanD)∈P. For any deletion instruction (λ, A, λ;q)ein cell p, the matrix (p→q, A →λ)∈P. Three additional matrices (h→λ), (D→λ) and (S→ q0Da1D· · · DamD) (w=a1· · · am) shall be also added to P. The above construction correctly simulates the system Π. Indeed, symbols Drepresent placeholders for all possible insertions. The first rule in the matrix permits simulates the navigation between cells. Nevertheless, minimal context-free insertion-deletion systems with priorities do generate PsRE. This is especially clear for the tissue P systems: jumping to an instruction corresponds to sending a string to the associated region, and the entire construction is a composition of graphs shown in Figure 1. The decrement instruction works correctly because of priority of deletion over insertion. /.-,()*+ p (λ,Ak,λ;q)a// (λ,Ak,λ;r)a ²² /.-,()*+ q /.-,()*+ r /.-,()*+ p (λ,Ak,λ;q)e// (λ,N,λ;p0)a ²² /.-,()*+ q /.-,()*+ p0 (λ,N,λ;r)e///.-,()*+ r Fig. 1. Simulating p: (ADD(k), q, r) (left) and p: (SUB(k), q, r) (right). We now give a more sophisticated proof for the tree-like membrane structure. Theorem 5. PsSP∗(ins0,0 1< del0,0 1) = P sRE. Proof. The proof is done by showing that for any register machine M= (n, Q, q0, h, P) there is a P system Π∈P sSP∗(ins0,0 1< del0,0 1) with Ps(M) = Ps(Π), and the result follows from the existence of register machines generating PsRE. Let Q+(Q−) be the sets of labels of increment (conditional decrement, respectively) instructions of a register machine, and let Q=Q+∪Q−∪ {h}represent all labels. Consider a P system with alphabet Q∪ {Ai|1≤i≤d}∪{Y}and the following structure (illustrated in Figure 2) µ= [ [ [ Y p∈Q+ µhp+iY p∈Q− µhp−i ]3]2]1,where µhp+i= [ [ [ ]p+ 3]p+ 2]p+ 1 , p −increment, µhp−i = [ [ [ ]p− 3]p− 2[ [ ]p0 3]p0 2]p− 1 , p −conditional decrement. P Systems with Minimal Insertion and Deletion 15 /.-,()*+ 1 /.-,()*+ 2 L L L L L L for every p∈Q+/.-,()*+ 3 iiiiiiiiiiii U U U U U U U U U U U U U/.-,()*+ 4for every p∈Q− /.-,()*+p+ 1 /.-,()*+p− 1 U U U U U U U U U U U U /.-,()*+p+ 2 /.-,()*+p− 2 /.-,()*+p0 2 /.-,()*+p+ 3 /.-,()*+p− 3 /.-,()*+p0 3 ____ Â Â Â Â Â Â Â Â Â Â Â Â ____ __________ Â Â Â Â Â Â Â Â Â Â Â Â __________ Fig. 2. Membrane structure for Theorem 5. The structures in the dashed rectangles are repeated for every instruction of the register machine. Initially there is a single string q0in membrane 3. The rules are the following. R1={1 :(λ, Y, λ;out)e}, R2={2.1 :(λ, Y, λ;out)a,2.2 :(λ, Y, λ;in4)e}, R3={3.1 :(λ, p, λ;inp+ 1)e|p∈Q+}∪ {3.2 :(λ, p, λ;inp− 1)e|p∈Q−} ∪ { 3.3 :(λ, Y, λ;here)e,3.4 :(λ, h, λ;out)e}, For any instruction p: (ADD(k), q, s), Rp+ 3=∅and Rp+ 1={a.1.1 :(λ, Ak, λ;inp+ 2)a, a.1.2 :(λ, Y, λ;out)a}, Rp+ 2={a.2.1 :(λ, q, λ;out)a, a.2.10:(λ, s, λ;out)a, a.2.2 :(λ, q, λ;inp+ 3)e, a.2.20:(λ, s, λ;inp+ 3)e}, For any instruction p: (SUB(k), q, s), Rp− 3=Rp0 3=∅and Rp− 1={e.1.1 :(λ, Ak, λ;inp− 2)e, e.1.2 :(λ, Y, λ;inp− 2)a, e.1.3 :(λ, Y, λ;out)e}, Rp− 2={e.2.1 :(λ, q, λ;out)a, e.2.2 :(λ, q, λ;inp− 3)e, e.2.3 :(λ, s, λ;inp− 3)e, e.2.4 :(λ, Y, λ;here)a}, Rp0 2={e.3.1 :(λ, s, λ;out)a, e.3.2 :(λ, q, λ;inp0 3)e, e.3.3 :(λ, s, λ;inp0 3)e}. Configurations (p, x1,· · · , xn) of Mare encoded by strings ∆(pAx1 1· · · Axn nYt), t≥0, in membrane 3. We say that such strings have a simulating form. Clearly, in the initial configuration the string is already in the simulating form. To prove that system Πcorrectly simulates Mwe prove the following claims: 1. For any transition (p, x1,· · · , xn) =⇒(q, x0 1,··· , x0 n) in Mthere exists a computation in Πfrom the configuration containing ∆(pAx1 1···Axn nYt) in membrane 3 to the configuration containing ∆(qAx0 1 1· · · Ax0 n nYt0), t0≥0, in membrane 3 such that during this computation membrane 3 is empty in all intermediate steps and, moreover, this computation is unique. 16 A. Alhazov et al. 2. For any successful computation in Π(yielding a non-empty result), membrane 3 contains only strings of the above form. 3. The result (x1,· · · , xn) in Πis obtained if and only if a string of form ∆(hAx1 1· · · Axn n) appears in membrane 3. Now we prove each claim from above. Consider a string ∆(pAx1 1· · · Axn nYt), t≥0, in membrane 3 of Π. Take an instruction p: (ADD(k), q, s)∈P. The only applicable rule in Πis from group 3.1 (in the future we simply say rule 3.1) yielding the string ∆(Ax1 1· · · Axn nYt) in membrane p+ 1. After that rule a.1.1 is applied yielding string ∆(Ax1 1···Axk+1 k· · · Axn nYt) in membrane p+ 2. After that one of rules a.2.1 or a.2.10is applied; then rule a.1.2 yields one of strings ∆(zAx1 1· · · Axk+1 k· · · Axn nYt+1), z∈ {q, s}, which is in the simulating form. Now suppose that there is an instruction p: (SUB(k), q, s)∈P. Then the only applicable rule in Πis 3.2 which yields the string ∆(Ax1 1· · · Axn nYt) in membrane p− 1. Now if xk>0, then, due to the priority, rule e.1.1 will be applied followed by application of rules e.2.4, e.2.1 and e.1.3 which yields the string ∆(qAx1 1···Axk−1 k· · · Axn nYt0) that is in the simulating form. If xk= 0, then rule e.1.2 will be applied (provided that all symbols Ywere previously deleted by rule 3.3), followed by rules e.3.1 and e.1.3 which leads to the string ∆(sAx1 1· · · Axn n) that is in the simulating form. To show that membrane 3 is empty during the intermediate steps, we prove the following invariant: Invariant 1 During a successful computation, any visited membrane p+ 1or p− 1is visited an even number of times as follows: first a string coming from membrane 3 is sent to an inner membrane (p+ 2,p− 2or p0 2) and after that a string coming from an inner membrane is sent to membrane 3. Indeed, since there is only one string in the initial configuration, it is enough to follow only its evolution. Hence, a string may visit the node p+ 1or p− 1only if in the previous step symbol pwas deleted by one of rules 3.1 or 3.2. If one of rules a.1.2 or e.1.3 is applied, then membrane 3 will contain a string of form ∆(Ax1 1···Axn nYt) which cannot evolve anymore because all rules in membrane 3 imply the presence of a symbol from the set Q. Hence, the string is sent to an inner membrane. In the next step the string will return from the inner membrane by one of rules a.2.1, a.2.10,e.2.1 or e.3.1 inserting a symbol from Q. If the string enters an inner membrane again, then it will be sent to a trap membrane (p+ 3,p− 3or p0 3) by rules deleting symbols from Q. Hence the only possibility is to go to membrane 3 (a string that visited membrane p− 2will additionally use rule e.2.4). For the second claim, it suffices to observe that the invariant above ensures that in membrane 3 only one symbol from Qcan be present in the string. The third claim holds since a string may move to membrane 2 if and only if the final label hof Mappears in membrane 3. Then, the string is checked for the absence of symbols Yby rule 2.2 (note that symbols Ycan be erased in membrane 3 by rule 3.3) and sent to the environment by rules 2.1 and 1. P Systems with Minimal Insertion and Deletion 17 By induction on the number of computational steps we obtain that Πsimulates any computation in M. Claim 1 and 2 imply it is not possible to generate other strings and Claim 3 implies that the same result is obtained. We remark that an empty string may be obtained during the proof. This string can still evolve using insertion rules. If we would like to forbid such evolutions, it suffices to use a new symbol, e.g., X, in the initial configuration, add new surrounding membrane and a rule that deletes Xfrom it. 4 Small Contextual Insertion-Deletion P Systems Although Theorem 5 shows that the systems from the previous section are quite powerful, they cannot generate RE without control on the place where a symbol is inserted. Once we allow a context in insertion and deletion rules, they can. Theorem 6. LSP(ins0,1 1< del0,0 1) = RE. Proof. We simulate a register machine with WRITE instructions. We implement this instruction as an ADD instruction, except the added symbol has to be inserted to the left of a special marker, deleted at the end, as follows: •Replace any writing instruction p: (W RITE(A), q, s), A∈T, of the machine by instructions p: (ADD(A), q, s), considering output symbols Alike new dummy registers. Construct the system Πas in Theorem 5. •Change the initial string in membrane 3 to q0M; •Replace rules a.1.1 ((λ, A, λ;inp+ 2)a∈Rp+ 1) by (λ, A, M;inp+ 2)afor A∈T; •Surround membrane 1 by a new skin membrane sand add to it the following rule Rs={(λ, M, λ;out)e}. It is easy to see that the above construction permits to correctly simulate the register machine with writing instructions. Taking Min the left context yields the mirror language. Since RE is closed with respect to the mirror operation we get the following corollary: Corollary 2. LSP(ins1,0 1< del0,0 1) = RE. A similar result holds if contextual deleting operation is allowed. Theorem 7. LSP∗(ins0,0 1< del1,0 1) = RE. Proof. As in Theorem 6, we use the construction from Theorem 5. However, an additional membrane is needed to simulate the writing instructions. We modify the construction of Theorem 5 as follows. Let Qsbe the set of labels of WRITE instructions of a register machine. We add the following substructures µhpsiinside membrane 3 (shown in Figure 3):