P Systems with Minimal Left and Right Insertion and Deletion

P Systems with Minimal Left and Right Insertion and Deletion Rudolf Freund1, Yurii Rogozhin2, and Sergey Verlan3 1Faculty of Informatics, Vienna University of Technology Favoritenstr. 9, 1040 Vienna, Austria Email: [email protected] 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD-2028, Moldova Email: [email protected] 3LACL, D´epartement Informatique, Universit´e Paris Est 61, av. G´en´eral de Gaulle, 94010 Cr´eteil, France Email: [email protected] Summary. In this article we investigate the operations of insertion and deletion performed at the ends of a string. We show that using these operations in a P systems framework (which corresponds to using specific variants of graph control), computational completeness can even be achieved with the operations of left and right insertion and deletion of only one symbol. 1 Introduction The operations of left and right insertion and deletion that we consider in this article correspond to the operations of left and right concatenation and quotient with a finite language. While these operations are known for a long time, their joint investigation in a distributed framework originates from the area of natural computing, where they were used in the context of networks of evolutionary processors (NEP) [7]. Such networks are a special type of networks of language processors [6] that feature a set of (rewriting) nodes rewriting languages and after that redistributing some regular subsets between the nodes. In networks of evolutionary processors, the rewriting operations are replaced by three types of operations having a biological motivation: insertion, deletion, and mutation (substitution). The corresponding systems are quite powerful and we refer to [8] for more details. The redistribution of the node contents based on a regular condition is a very powerful operation. Accepting hybrid networks of evolutionary processors (AHNEP) replace this condition by random context conditions, however, the set 124 R. Freund, Y. Rogozhin, S. Verlan of operations is changed and now includes the insertion and deletion operations at the extremities of the strings; we refer to [21, 9] for more details on AHNEP. The operations of insertion and deletion on the extremities of a string can also be seen as a particular case of a more general variant, where insertion and deletion can be performed anywhere in the string. The insertion operation defined in such a way was first considered in [14, 15] and after that related insertion and deletion operations were investigated in [17, 18]. Another generalization of the insertion and deletion operations that involves the checking of contexts for the insertion and deletion was considered with a linguistic motivation in [13, 20] and with a biological motivation in [4, 5, 18, 26]. Generally, if the length of the contexts and/or of the inserted and deleted strings are big enough, then the insertion-deletion closure of a finite language leads to computational completeness. There are numerous results establishing the descriptional complexity parameters sufficient to achieve this goal, we refer to [31, 30] for an overview of this area. Some descriptional complexity parameters lead to variants that are not computationally complete. An investigation of insertion and deletion operations combined with regulating mechanisms was done for these cases, more precisely, with the graph-controlled, the matrix, and the random-context controls [11, 28, 16]. As it was shown in these articles, in most of the cases the additional control leads to computational completeness. The graph-controlled regulation is of particular interest, as it can be related to the notion of P systems. Such systems formalize the functioning of a living cell that topologically delimits processing units by membranes, thus leading to a tree (or graph) structure of processing nodes. The elements processed in some node (membrane) then are distributed among the neighbors in the structure. We refer to [24, 25] and to the web page [29] for more details on P systems. In the case of the operations of insertion and deletion acting on strings this directly corresponds to a graph control where the control nodes correspond to the membranes. The research on context-free insertion and deletion (i.e., without contextual dependency) shows that if the lengths of the inserted and deleted strings are 2 and 3 (or 3 and 2), respectively, then the insertion-deletion closure of finite languages is computationally complete [22]. When one of these parameters is decreased, this result is not true anymore [32]; moreover, even the graph-controlled variant cannot achieve computational completeness [19]. This changes when a graph control with appearance checking is used [1] or in the case of a random context control [16]. In both variants, minimal operations (involving only one symbol) were considered, leading to RE (the family of recursivey enumerable languages) in the case of setcontrolled random context conditions and to PsRE (the family of Parikh sets of RE) in the case of graph control with appearance checking. We note that the operations of left and right insertion and deletion are incomparable with normal insertion and deletion: because of the positional information, the regular language a+b+can be obtained even with left and right insertions of only one symbol, yet not when insertions are possible at arbitrary positions in the string. On the other hand, the Dyck language cannot be obtained when insertion P Systems with Minimal Left and Right Insertion and Deletion 125 is only possible at the ends of the strings, while with normal insertion this can be done easily. In [1, 3], left and right insertion and deletion operations (under the name of exo-insertion and -deletion) were considered in the P systems framework (i.e., with a graph control) and it was shown that systems with insertion of strings of length 2 (respectively 1) and deletion of strings of length 1 (respectively 2) lead to computational completeness. In the case of minimal insertion and deletion (i.e., of only one symbol), a priority of deletion over insertion (corresponding to an appearance check) was used to show computational completeness. In this article we continue these investigations and we consider P systems with minimal left and right insertion and deletion and prove that computational completeness can be achieved even in this case, with the structure of the P system we need being matrix-like. We also directly show that matrix grammars using minimal left insertion and minimal right deletion rules are computationally complete (with matrices of length at most 3). Moreover, we also prove that using an additional minimal mutation operation (substitution of one symbol by another one) allows for reducing the height of the tree structure of the P system to the minimum size 1. 2 Preliminaries After some preliminaries from formal language theory, we define the string rewriting rules to be used in this paper. As string rewriting systems, we will consider Post systems, matrix grammars, and sequential P systems. Moreover, we will give some examples and preliminary results to illustrate our definitions. The set of non-negative integers is denoted by N. An alphabet Vis a finite nonempty set of abstract symbols. Given V, the free monoid generated by Vunder the operation of concatenation is denoted by V∗; the elements of V∗are called strings, and the empty string is denoted by λ;V∗\ {λ}is denoted by V+. Let {a1, ..., an}be an arbitrary alphabet; the number of occurrences of a symbol ai in xis denoted by |x|ai; the number of occurrences of all symbols from Vin xis denoted by |x|. The family of recursively enumerable string languages is denoted by RE. For more details of formal language theory the reader is referred to the monographs and handbooks in this area as [10, 27]. We here consider string rewriting rules only working at the ends of a string: Post rewriting rule P[x/y] with x, y ∈V∗:P[x/y] (wx) = yw for w∈V∗. Left substitution SL[x/y] with x, y ∈V∗:SL[x/y] (xw) = yw for w∈V∗. Right substitution SR[x/y] with x, y ∈V∗:SR[x/y] (wx) = wy for w∈V∗. If in a (left or right) substitution SL[x/y] or SR[x/y]xis empty, then we call it an insertion and write IL[y] and IR[y], respectively; if in a (left or right) substitution SL[x/y] or SR[x/y]yis empty, then we call it a deletion and write DL[x] and DR[x], respectively. If we only insert one symbol a, then we will also write +a,a+, −a, and a−for IL[a], IR[a], DL[a], and DR[a], respectively. 126 R. Freund, Y. Rogozhin, S. Verlan In general, a (string rewriting) grammar Gof type Xis a construct (V, T, A, P ) where Vis a set of symbols,T⊆Vis a set of terminal symbols,A∈V+is the axiom, and Pis a finite set of rules of type X. Each rule p∈Pinduces a relation =⇒p⊆V∗×V∗;pis called applicable to a string x∈V∗if and only if there exists at least one string y∈V∗such that (x, y)∈=⇒p; we also write x=⇒py. The derivation relation =⇒Gis the union of all =⇒p, i.e., =⇒G=∪p∈P=⇒p. The reflexive and transitive closure of =⇒Gis denoted by ∗ =⇒G. The language generated by Gis the set of all terminal strings derivable from the axiom, i.e., L(G) = {v∈T∗|A∗ =⇒Gv}. The family of languages generated by grammars of type Xis denoted by L(X). In general, we write Sk,m Rfor a type of grammars using only substitution rules SR[x/y] with |x| ≤ kand |y| ≤ m. In the same way, we define the type Sk,m Lfor a type of grammars using only substitution rules SL[x/y] with |x| ≤ kand |y| ≤ m, as well as the types Im L,Im R,Dk L, and Dk R, respectively. The type DkImallows for the deletion of strings with length ≤kand for the insertion of strings with length ≤m. If, in addition, we also allow substitutions SR[x/y] with |x| ≤ k′and |y| ≤ m′, we get the type DkImSk′m′; we observe that the type DkImSk′m′is subsumed by the type Sk′m′if k≤k′and m≤m′. If we allow the parameters k and/or mto be arbitrarily large, we just omit them, e.g., DI is the type allowing to use deletions and insertions of strings of arbitrary lengths. Example 1. Let G= (V, T, A, P ) be a regular grammar, i.e., the rules in Pare of the form A→bC and A→λwith A, C ∈V\Tand b∈T. Then the grammar G′= (V, T, A, {SR[A/y]|A→y∈P}) with substitution rules generates the same language as G, i.e., L(G′) = L(G). Hence, with REG denoting the family of regular languages, we obviously have got REG ⊆ L (S1,2 R). It is not difficult to check that grammars of type D1I1S1have a rather limited computational power. Indeed, we can show the following representation of languages generated by grammars of type D1I1S1: Theorem 1. Every language L⊆T∗in L(D1I1S1)can be written in the form T∗ lST∗ rwhere Tl, Tr⊆Tand Sis a finite subset of T∗. Proof. Let G= (V, T, A, P ) be a grammar of type D1I1S1and let N:= V\T. We first construct the start set Sas follows: Consider all possible derivations in Gfrom Awith only using substitutions and deletions, but without loops, i.e., no string is allowed to appear more than once in such a derivation, which means that all these derivations are of bounded length (bounded by the number of strings in Vof length at most |V|).Then Sconsists of all terminal strings obtained in this way (finding these strings is a finitely bounded process, as to each of the possible strings in Vof length at most |V|, at most |P|rules can be applied). A symbol from Nremaining inside a string blocks that string from ever becoming terminal by applying rules from P, and deletion of a symbol can be avoided by P Systems with Minimal Left and Right Insertion and Deletion 127 just not introducing the symbol which by a sequence of minimal substitutions would lead to the symbol to be deleted. Hence, for constructing the sets Tl(Tr, respectively) we can restrict ourselves to the terminal symbols beither directly inserted by minimal insertion rules Il[b] (Ir[b], respectively) or obtained by a sequence of one minimal insertion together with a bounded (by |V|) number of minimal substitutions Sl[a/b] (Sr[a/b], respectively). Therefore, in sum L(G) can be written as the finite union of languages generated by grammars of type I1, i.e., L(G) = ∪w∈SL(Gw) where Gw= (T, T, w, {Il[b]|b∈Tl}∪{Ir[b]|b∈Tr}). In fact, this representation of languages in L(D1I1S1)means that for the type D1I1S1we could forget minimal deletions and substitutions and instead consider finite subsets of axioms instead of a single axiom. Putting an Ain front of the types for this variant of grammars, we just have proved that L(A-D1I1S1)=L(A-I1). 2.1 Post Systems APost system is a grammar using only Post rewriting rules (a grammar of type PS). A Post system (V, T, A, P) is said to be in normal form (a grammar of type PSNF ) if and only if the Post rewriting rules P[x/y] in Pare only of the forms P[ab/c], P[a/bc], P[a/b], and P[a/λ], with a, b, c ∈V. A Post system (V, T, A, P) is said to be in Z-normal form (a grammar of type P SZNF) if and only if it is in normal form and, moreover, there exists a special symbol Z∈V\Tsuch that •Zappears only once in the string xof a Post rewriting rule P[x/y], and this rule is P[Z/λ]; •if the rule P[Z/λ] is applied, the derivation in the Post system stops yielding a terminal string; •a terminal string can only be obtained by applying the rule P[Z/λ]. Although basic results concerning Post systems are folklore since many years, e.g., see [23], we need the special Z-normal form for the proof of our main theorem; the following result is an immediate consequence of the proof given in [12] for Lemma 1 there: Theorem 2. For every recursively enumerable language L⊆T∗there exists a Post rewriting system G,G= (V, T, A, P), in Z-normal form such that L(G) = L, i.e., L(PS) = L(PSNF) = L(PSZNF) = RE. 2.2 Matrix Grammars Amatrix grammar of type Xis a construct GM= (G, M) where G= (V, T, A, P) is a grammar of type X,Mis a finite set of sequences of the form (p1, . . . , pn), n≥1, of rules in P. For w, z ∈V∗we write w=⇒GMzif there are a matrix 128 R. Freund, Y. Rogozhin, S. Verlan (p1, . . . , pn) in Mand objects wi∈V∗,1≤i≤n+ 1, such that w=w1, z=wn+1,and, for all 1 ≤i≤n,wi=⇒Gwi+1. The maximal length nof a matrix (p1, . . . , pn)∈Mis called the degree of GM. L(GM) = {v∈T∗|A=⇒∗ GMv}is the language generated by GM. The family of languages generated by matrix grammars of type X(of degree at most n) is denoted by L(X-MAT) (L(X-MATn)). Theorem 3. L(D2I2-MAT2)=L(D1I1-MAT3)=L(PSNF) = RE. Proof. From Theorem 2 we know that L(PSNF) = RE, hence, we will only show that for every Post system G= (V, T, A, P) in normal form we are able to construct equivalent matrix grammars G1= (G, M1) and G2= (G, M2) of type D2I2and of type D1I1, respectively: M1={(DR[x], IL[y]) |P[x/y]∈P}, M2={(DR[b], DR[a], IL[c]) |P[ab/c]∈P} ∪ {(DR[a], IL[c], IL[b]) |P[a/bc]∈P} ∪ {(DR[a], IL[b]) |P[a/b]∈P} ∪ {(DR[a]) |P[a/λ]∈P}. As each rule in Gis directly simulated by a matrix in M1and in M2, respectively, we immediately infer L(G) = L(G1) = L(G2).  Whereas the matrices in M1are only of length 2, the degree of M2is 3; it remains as an open question whether also with rules of type D1I1we could decrease the degree to 2 or not; we conjecture that the answer is no. As we have shown in Theorem 1, with grammars using rules of type D1I1S1we are not able to obtain RE, we even remain below the regular language class; hence, we need such regulating mechanisms as matrices to reach computational compleness. 2.3 P Systems We now introduce another variant to guide the derivations in a grammar using rules of those types introduced above, i.e., specific variants of left and right substitution rules. A(sequential) P system of type Xwith tree height nis a construct Π= (G, µ, R, i0) where G= (V, T, A, P ) is a grammar with rules of type Xand •µis the membrane (tree) structure of the system with the height of the tree being n(µusually is represented by a string containing correctly nested marked parentheses); we assume the membranes, i.e., the nodes of the tree representing µ, being uniquely labelled by labels from a set Lab; •Ris a set of rules of the form (h, r, tar) where h∈Lab,r∈P, and tar, called the target indicator, is taken from the set {here, in, out}∪{inj|1≤j≤n}; the rules assigned to membrane hform the set Rh={(r, tar)|(h, r, tar)∈R}, i.e., Rcan also be represented by the vector (Rh)h∈Lab; P Systems with Minimal Left and Right Insertion and Deletion 129 •i0is the initial membrane where the axiom Ais put at the beginning of a computation. As we only have to follow the trace of a single string during a computation of the P system, a configuration of Πcan be described by a pair (w, h) where wis the current string and his the label of the membrane currently containing the string w. For two configurations (w1, h1) and (w2, h2) of Πwe write (w1, h1) =⇒Π(w2, h2) if we can pass from (w1, h1) to (w2, h2) by applying a rule (h1, r, tar)∈R, i.e., w1=⇒rw2and w2is sent from membrane h1to membrane h2according to the target indicator tar. More specifically, if tar =here, then h2=h1; if tar =out, then the string w2is sent to the region h2immediately outside membrane h1; if tar =inh2, then the string is moved from region h1to the region h2immediately inside region h1; if tar =in, then the string w2is sent to one of the regions immediately inside region h1. A sequence of transitions between configurations of Π, starting from the initial configuration (A, i0), is called a computation of Π. A halting computation is a computation ending with a configuration (w, h) such that no rule from Rhcan be applied to wanymore; (w, h) is called the result of this halting computation if w∈T∗.L(Π), the language generated by Π, consists of all strings over Twhich are results of a halting computation in Π. By L(X-LP) (L(X-LP⟨n⟩)) we denote the family of languages generated by P systems (of tree height at most n) using rules of type X. If only the targets here, in, out are used, then the P system is called simple, and the corresponding families of languages are denoted by L(X-LsP) (L(X-LsP ⟨n⟩)). Example 2. Let Π= (G, [1[2]2[3]3[4]4]1, R, 1) be a P system of type D1 RI2 L with G= ({a, B},{a},{DR[a], DR[B], IL[aa], IL[B]}, aB), R={(1, DR[a], in2),(1, DR[B], in3),(1, DR[B], in4)} ∪ {(2, IL[aa], out),(3, IL[B], out)} The computations in Πstart with aB in membrane (region) 1. In general, starting with a string a2nB,n≥0, in membrane 1, we may either delete B by the rule (1, DR[B], in4), getting a2nas the terminal result in the elementary membrane 4 (a membrane is called elementary if and only if it contains no inner membrane) or delete Bby the rule (1, DR[B], in3). With the string a2narriving in membrane 3, we get Ba2nin membrane 1 by the rule (3, IL[B], out). Now we double the number of symbols aby applying the sequence of rules (1, DR[a], in2) and (3, IL[aa], out) 2ntimes, finally obtaining a2n+1 B. Hence, in sum we get L(Π) = {a2n|n≥0}for the language generated by this P system µof type D1 RI2 L. 130 R. Freund, Y. Rogozhin, S. Verlan 3 Computational Completeness of P Systems with Minmal Substitution Rules In this section we consider several variants of P systems with substitution rules of minimal size, the main result showing computational completeness for simple P systems with rules of type D1I1. Yet first we show that for any recursively enumerable language we can construct a P system, with the height of the tree structure being only 1 (which is the minimum possible according to Theorem 1), of type D1 RI1 LS1 R, i.e., using minimal right insertions and minimal right deletions and mutations (substitutions). Theorem 4. L(D1 RI1 LS1 R-LP⟨1⟩)=RE. Proof. From Theorem 2 we know that L(PSZNF) = RE, hence, we will only show that for every Post system G= (V, T, A, P) in Z-normal form we are able to construct equivalent P system Πof type D1 RI1 LS1 R. We assume that the rules in Pare labelled in a unique way by labels from a finite set Lab with 1 /∈Lab and z∈Lab. We now construct a P system Π,Π= (G′, µ, R, 1), with a flat tree structure µof height 1, i.e., with the outermost membrane (the so-called skin membrane) being labelled by 1, and all the other membranes being elementary membranes inside the skin membrane being labelled by labels from Lab′={1,#} ∪ {l|l:p∈Lab} ∪{¯ h|h:P[ah/bhch]∈P}∪{¯ h|h:P[ahbh/ch]∈P}. G′= (V′, T, A, P′), V′={x, ¯xl|x∈V, l ∈Lab}∪ {#}, and P′contains the minimal left insertion, right deletion, and right substitution rules contained in the rules of Ras listed in the following: h:P[ahbh/ch]: (1, DR[bh], inh), (h, SR[ah/¯ah h], out), (h, IL[#] , out), (1, DR[¯ah h], in¯ h),(¯ h, IL[ch], out); h:P[ah/bhch]: (1, SR[ah/¯ah h], inh), (h, IL[ch], out), (1, DR[¯ah h], in¯ h),(¯ h, IL[bh], out); h:P[ah/bh]: (1, DR[ah], inh), (h, IL[bh], out); h:P[ah/λ]: (1, SR[ah/ah], inh), (l, DR[ah], out), for ah=Z; z:P[Z/λ]: (DR[Z], inz); the additional membrane # is used to trap all computations not leading to a terminal string in an infinite loop by the rules (1, IL[#] , in#) and (#, IL[#] , out); for this purpose, the rule (h, IL[#] , out) is used in case of h:P[ahbh/ch], too. Due to the features of the underlying Post system in Z-normal form, all terminal strings from L(G) can be obtained as final results of a halting computation in the elementary membrane z, whereas all other possible computations in Πnever halt, finally being trapped in an infinite loop guaranteed by the rules leading into and out from membrane #. Hence, in sum we get L(Π) = L(G). Summarizing the results of Theorems 1 and 4, we get: P Systems with Minimal Left and Right Insertion and Deletion 131 Corollary 1. L(D1I1S1)=L(D1I1S1-LP⟨0⟩)⊂REG ⊂ L(D1 RI1 LS1 R-LP⟨n⟩)=RE for all n≥1. If we want to restrict ourselves to the simple targets here, in, out, then we have to use a more difficult proof technique than in the proof of Theorem 4. Theorem 5. L(D1I1-LsP⟨8⟩)=RE. Proof. In order to show the inclusion RE ⊆ L (D1I1-LsPLsP⟨8⟩), as in the proof of Theorem 4 we start from a Post system G= (V, T, A, P) in Z-normal form with assuming the rules in Pto be labelled in a unique way by labels from a finite set Lab with 1 /∈Lab and z∈Lab and construct an equivalent simple P system Π, Π= (G′, µ, R, 1), of type D1I1, with G′= (V′, T, A, P ′) and V′=V∪VR∪ {S},VR={D, E, F, H, J, K, M}, P′={+X, −X|X∈V∪ {S}} ∪ {X+, X− | X∈V∪VR}, as follows: The membrane structure µconsists of the skin membrane 1 as well as of linear structures needed for the simulation of the rules in G: For every rule h:P[ahbh/ch] and every rule h:P[ah/bhch] in Pwe need a linear structure of 8 membranes [(h,1) [(h,2) ... [(h,8) ](h,8) ...](h,2) ](h,1) and for every rule h:P[ah/bh] and every rule h:P[ah/λ] in Pwe need a linear structure of 6 membranes [(h,1) [(h,2) ... [(h,6) ](h,6) ...](h,2) ](h,1) ; moreover, for getting the terminal results, we need the linear structure of 3 membranes [(z,1) [(z,2) [(z,3) ](z,3) ](z,2) ](z,1) . The simulations of the other rules from Pare accomplished by the procedures as shown in the tables below, where the columns have to be interpreted as follows: in the first column, the membrane (label) his listed, in the second one only the rule p∈Pis given, which in total describes the rule (h, p, in)∈R, whereas the rule pin the fifth column has to be interpreted as the rule (h, p, out)∈R.; the strings in the third and the fourth column list the strings obtained when going up in the linear membrane structure with the rules (h, p, in) from column 2 and going down with the rules (h, p, out) from column 5, respectively. The symbol Fcannot be erased anymore, hence, whenever Fhas been introduced, at some moment, the computation will land in an infinite loop with only introducing more and more symbols F. The main idea of the proof is that we choose the membrane to go into by the rule (1, K+, in) in a non-deterministic way. The goal is to reach the terminal membrane (z, 3) starting with a string wZ,w∈T∗, in the skin membrane: (z, 3) w (z, 2) Z−wZ F+ (z, 1) K−wZK wF F+ 1K+wZ wFF Getting the terminal string w∈T∗ The tables below are to be interpreted in the same way as above; yet now we only list the results of correct simulations in column 4 and omit the results of adding the trap symbol F. Moreover, the rule D−in the skin membrane is the only one in the whole system which uses the target here, i.e., it has to be interpreted as (1, D−, here).