Membrane Computing Schema: A New Approach to Computation Using String Insertions

Membrane Computing Schema: A New Approach to Computation Using String Insertions Mario J. Pérez-Jiménez and Takashi Yokomori Abstract In this paper, we introduce the notion of a membrane computing schema for string objects. We propose a computing schema for a membrane network (i.e., tissue-like membrane system) where each membrane performs unique type of operations at a time and sends the result to others connected through the channel. The distinguished features of the computing models obtained from the schema are: 1. only context-free insertion operations are used for string generation, 2. some membranes assume filtering functions for structured objects (molecules), 3. generating model and accepting model are obtained in the same schema, and both are computationally universal, 4. several known rewriting systems with universal computability can be reformulated by the membrane computing schema in a uniform manner. The first feature provides the model with a simple uniform structure which facilitates a biological implementation of the model, while the second feature suggests further feasibility of the model in terms of DNA complementarity. Through the third and fourth features, one may have a unified view of a variety of existing rewriting systems with Turing computability in the framework of membrane computing paradigm. 1 Introduction In the theory of bio-inspired computing models, membrane systems (or P systems) have been widely studied from various aspects of the computability such as the optimal system designs, the functional relations among many ingredients in different levels of computing components, the computational complexity and so forth. Up to the present, major concerns are focused on the computational capability of multisets of certain objects in a membrane structure represented by a rooted tree, and there are a relatively limited amount of works in the membrane structure of other types (like a network or graph) on string objects and their languages: those are, M.J. Pérez-Jiménez () Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda Reina Mercedes s/n, 41012 Sevilla, Spain e-mail: [email protected] for example, in the context of P system on graph structure [15], of the tissue P systems [11], and of spiking neural P systems [3,7]. On the other hand in DNA computing theory, a string generating device called insertion-deletion system has been proposed and investigated from the unique viewpoint of non-rewriting nature in generating string objects [10,14]. Among others, string insertion operation with no context is of our particular interests, because of the relevance to biological feasibility in terms of DNA sequences. In this paper, we are concerned with tissue-like membrane systems with string insertion operations and investigate the computational capability of those systems. By using the framework of tissue-like membrane systems, however, our major focus is on studying the new aspects of the computational mechanisms used in a variety of existing models based on string rewriting. To this aim, we propose the notion of a membrane computing schema which provides a unified view and framework to investigate new aspects of the variety of computational mechanisms. More specifically, let Mbe a given computing device (grammar or machine) based on string manipulation. Then by a membrane computing schema Π, we represent the core structure of Min question. At the same time, we also consider an interpretation Ito Πwhich specifies the details of M.Inthis manner, we are able to have Mthat is embodied as a tissue-like membrane system I(Π)with string insertion operation. The advantages of this schematic approach to computing are the following: (1) High transparency of the computing mechanism is obtained by separating the skeletal (core) part from other detailed specificity of the computation. (2) Structural modularity of the computing model facilitates our better understanding of the computing mechanism. With this framework, we will present not only new results of the computing models with universal computability but also a unified view of those models from the framework of tissue-like membrane system with string insertion operations. 2 Preliminaries We assume the reader to be familiar with all formal language notions and notations in standard use. For unexplained details, consult, e.g., [14,16]. For a string xover an alphabet V(i.e., xin V∗), lg(x) denotes the length of x.For the empty string, we denote it by λ. For an alphabet V,V={a|a∈V}. A binary relation ρover Vis called an involution if ρis injective and ρ2is an identity (i.e., for any a∈V, if we write ρ(a)=a, then it holds that ρ(a) =a). A Dyck language Dover Vis a language generated by a context-free grammar G=({S},V,P,S), where P={S→SS,S →λ}∪{S→aSa|a∈V}and kis the cardinality of V. An insertion system [10] is a triple γ=(V,P,A), where Vis an alphabet, Ais a finite set of strings over Vcalled axioms, and Pis a finite set of insertion rules. An insertion rule over Vis of the form (u,x,v), where u,x,v ∈V∗. We define the relation → on V∗by w→ ziff w=w1uvw2and z=w1uxvw2for some insertion rule (u,x,v)∈P,w1,w2∈V∗. As usual →∗denotes the reflexive and transitive closure of →.Aninsertion language generated by γis defined as follows: L(γ ) ={w∈V∗|s→∗w,s ∈A}.An insertion rule of the form (λ,x,λ)is said to be context-free, and we denote it by λ→x. We denote by RE,CF,LIN,and RG the families of recursively enumerable languages, of context-free languages, of linear languages, and of regular languages, respectively. Amatrix grammar with appearance checking is a construct G=(N,T,S,M,F), where N,T are disjoint alphabets, S∈N,Mis a finite set of sequences of the form (A1→x1,...,An→xn),n≥1, of context-free rules over N∪T(with Ai∈N,xi∈(N ∪T) ∗, in all cases), and Fis a set of occurrences of rules in M(we say that Nis the non-terminal alphabet, Tis the terminal alphabet, Sis the axiom, while the elements of Mare called matrices). For w,z ∈(N ∪T) ∗,we write w⇒ zif there is a matrix (A1→x1,...,An→ xn)in Mand the strings wi∈(N ∪T) ∗,1≤i≤n+1, such that w=w1,z=wn+1, and for all 1 ≤i≤n, either wi=w iAiw i,wi+1=w ixiw i,forsomew i,w i∈(N ∪ T) ∗,orwi=wi+1,Aidoes not appear in wi, and the rule Ai→xiappears in F. (The rules of a matrix are applied in order, possibly skipping the rules in Fif they cannot be applied; we say that these rules are applied in the appearance checking mode.) If F=∅, then the grammar is said to be without appearance checking (and Fis no longer mentioned). We denote by ⇒∗the reflexive and transitive closure of the relation ⇒. The language generated by Gis defined by L(G) ={w∈T∗|S⇒∗w}.The family of languages of this form is denoted by MATac. When we use only grammars without appearance checking, then the obtained family is denoted by MAT.Itis known that MAT ⊂MATac =RE. A matrix grammar G=(N,T,S,M,F) is said to be in the binary normal form if N=N1∪N2∪{S,#}, with these three sets mutually disjoint, and the matrices in Mare of one of the following forms: 1. (S →XA), with X∈N1,A∈N2, 2. (X →Y,A →x), with X, Y ∈N1,A∈N2,x∈N2∪N2 2∪T∪{λ}, 3. (X →Y,A →#), with X, Y ∈N1,A∈N2, 4. (X →λ,A →x), with X∈N1,A∈N2,and x∈T∪{λ}. Moreover, there is only one matrix of type 1 and Fconsists exactly of all rules A→# appearing in matrices of type 3; # is a trap-symbol, once introduced, it is never removed. A matrix of type 4 is used only once, at the last step of a derivation. A matrix of type 3 is called appearance checking matrix rule. For each matrix grammar (with appearance checking) there effectively exists an equivalent matrix grammar (with appearance checking) in the binary normal form. (Note that the definition of the binary normal form presented here is a variant of the one in [5].) Arandom context grammar is a construct G=(N,T,S,P), where N,T are disjoint alphabets, S∈N,Pis a finite set of rules of the form (A →x,Q,R), where A→xis a context-free rule (A∈N,x ∈(N ∪T) ∗), Qand Rare subsets of N. For α, β ∈(N ∪T) ∗,we write α⇒ βiff α=uAv,β=uxv for some u, v ∈ (N ∪T) ∗,(A →x,Q,R) ∈Pand all symbols of Qappear in uv, and no symbol of Rappears in uv. We denote by ⇒∗the reflexive and transitive closure of the relation ⇒. The language generated by Gis defined by L(G) ={w∈T∗|S⇒∗w}.The family of languages of this form is denoted by RC. It is known that RC =RE [5]. Note that in what concerns the definitions above for matrix and random context grammars, we only deal with the type 2 (context-free) grammar as the core grammar. 3 Membrane Computing Schema, Interpretation and Languages We now introduce the notion of a membrane computing schema in a general form, then we will present a restricted version, from which a variety of specific computing models based on insertion operations and filtering can be obtained in the framework of a tissue-like membrane computing. That is, a membrane computing schema is given as a skeletal construct consisting of a number of membranes connected with synapses (or channels) whose structure may be taken as a kind of tissue P systems (e.g., [11]). 3.1 Membrane Computing Schema Amembrane computing schema of degree (p,k,t)is a construct Π=(V,T, Com,Ope,Fil,Syn,i s,Out), where •Vis a finite alphabet with an involution relation ρcalled the working alphabet. •Tis a subset of Vcalled the terminal alphabet. •Com ={Com1,...,Comp}is a finite set with pelements, called communication cells. •Ope ={Ope1,...,Opek}is a finite set with kelements, called operation cells. •Fil ={SF,FF}∪{FF1,...,FFt}is a finite set with (t+2)elements, called filtering cells. (More specifically, SF and FF are called structured filter and final filter, respectively, and FF1,...,FFtare called sub-filter cells). •Syn is a subset of (Com ×Ope)∪(Ope ×Com)∪(Com ×(SubFil ∪{SF})) ∪ ({FF}×Com)∪(SubFil ×Ope)∪{(SF,FF),(FF,Out)}, where SubFil = {FF1,...,FFt}, which determines the tissue membrane structure of Π. (See Fig. 1.) •is(=Com1)is the distinguished cell (to designate some specific role). •Out is the output cell (for obtaining the outputs). Fig. 1 Modular structure of membrane network in Π Remark (1) For i=1,...,p, each cell Comiserves as a communication channel, that is, any string xin the cell Comiis sent out to all the cells indicated by Syn. (2) For j=1,...,k, each cell Opejconsists of a finite number of rules {σj1,..., σjs}, where each σji is a string insertion operation of the form: λ→u, where u∈V∗. (3) SF and FF are associated with two languages LSF and LFF over V, respectively. Further, for =1,...,t, each cell FFis also associated with a language LFF. 3.2 Interpretation of Π In order to embody a membrane computing schema Π, we need to give further information for Πspecifying the initial configuration, each operation in Ope, and materializing the filtering cells SF,FF, and FF(1≤≤t). Let us call such a notion an interpretation Ito the schema Πwhich enables us to have an embodied computing model I(Π)that is feasible in a usual sense. In what follows, we use the following notation: Notation For any xin Com ∪SubFil ∪{FF}, let Syn-from(x) ={y|(x, y) ∈Syn}, and for any yin Ope ∪SupFil ∪{SF}, let Syn-to(y) ={x|(x, y) ∈Syn}. Formally, an interpretation I to Πof degree (p,k,t)is a construct I=w0,{R1,...,Rk},LSF,LFF,{LFF|1≤≤t}, where •w0is a string in V∗called the axiom, where Vis the working alphabet of Π. •Rispecifies a set of insertion operations used in Opej(for j=1,...,k) •LSF (LFF) materializes a concrete specification about the function of SF (FF, respectively). In practical operational phases (described below), we assume the following: 1. In the cell SF, each string is assumed to form a certain structure (e.g., structured molecule based on hybridization in terms of H-bonds via minimal energy principle). SF takes as input a string uover Vand allows it to filter through if it is in LSF (otherwise, a string uis lost). Then after building up a structured form suof u,SF removes all parts of structures from suand produces as output the concatenation of all remaining strings. The output vis sent out to the cell FF. 2. FF receives as input a string vover V(from SF). A string vfilters through if it is in LFF and is sent out to Out. Otherwise, it is sent out to all cells in Syn-from(FF). 3. Each FFreceives as input a string uover V. Then a string vfilters through if it is in LFFand is sent out to all cells in Syn-from(FF). Otherwise, it is lost. 4. Filtering applies simultaneously to all strings in the filtering cell. Note that in the case SubFil is empty in a given Π, an interpretation to Πis simply written as I=(w0,{R1,...,Rk},LSF,LFF). 3.3 Transitions and Languages Given a schema Πof degree (p,k,t)and an interpretation Ito Π,wenowhave a membrane system I(Π) based on string insertions. In what follows, we define a transition sequence of I(Π)and the language associated with I(Π). The (p+1)-tuple of languages over Vrepresented by (L1,...,Lp,Lout)constitutes a configuration of the system, where each Lirepresents the set of all strings in the cell Comi(for all i=1,...,p), and Lout is the set of strings presented in the output cell (of the system at some time instance). Let C1=(L1,...,Lp,Lout)and C2=(L1,...,Lp,Lout)be two configurations of the system. We define one transition from C1to C2in the following steps: (0) Pre-checking Step: For each =1,...,t, consider L[]=q i=1Li, where Syn-to(FF)={Com1,...,Comq}. Then each cell FFfilters out all strings of L[]that are not in LFF, and all strings that have passed through are sent to all the cells in Syn-from(FF). (In the case when t=0, i.e., SubFil =∅,this step is skipped.) (1) Evolution Step: For each j=1,...,k,letσj1,...,σjs be all the operations given in Opej. Suppose that we apply operations σji :λ→uji (1 ≤i≤s)toastringvwhich means that each σji is applied to vsimultaneously. Further, when we apply σji to v, the location in vto insert uji is non-deterministically chosen and the result σji(v) is considered as the set of all possible strings obtained from vby σji. (Note that if two or more rules share the same location to insert, then all possible permutations of those rules are considered to apply to the location.) The result of such an application of all operations in Opejto vis denoted by Opej(v). Let L(j) =d m=1Ljm, where Syn-to(Opej)∩Com ={Comj1,...,Comjd}. Then the total result performed by Opejto L(j) is defined as OpejL(j)= v∈L(j) Opej(v). This result is then sent out to all cells in Syn-from(Opej)simultaneously. (2) Filtering Step: For each i=1,...,p,let ˜ Li=r n=1Opejn(L(jn)), where Syn-from(Comi)={Opej1,...,Opejr}. Further, let Le=g m=1˜ Lim, where Syn-to(SF)={Comi1,...,Comig}. SF takes as input the set Leand produces as output a set of strings Lf. (Recall that in the cell SF, each string uis assumed to form a certain structure, and the output of SF is the reduced string by removing structural parts from uin LSF.) Then SF sends out Lfto FF. (Any element of Lethat was filtered off by SF is assumed to be lost.) Finally, the cell FF filters out strings of Lfdepending upon whether they are in LFF or not. All strings in Lfthat passed through FF are sent out to Out, while others are simultaneously sent to all Comiin Syn-from(FF)or they are all lost if Syn-from(FF)=∅. Let Lff be the set of all strings that were filtered off by FF. Then we define C2=(L1,...,Lp,Lout)by setting for each i=1,...,p Li=Lff if Comi∈Syn-from(FF), ˜ Liotherwise. Further, let Lout =Lout ∪Lf(Out), where Lf(Out)=Lf−Lff (the set of all strings that have passed through FF and been sent to Out). Remark (1) Each cell in Com not only provides a buffer for storing intermediate results in the computation process but also transmit them to the cells specified by Syn. (2) Each cell in Ope takes as input a set of strings Land applies insertion operations to L, and sends out the result to the cells specified by Syn. (3) Each filtering cell in Fil also takes as input a set of strings Land performs filtering of Lin a way previously described, and sends out the result to the cells specified by Syn. (4) The system has a global clock and counts time in such a way that every cell (including communication cells) takes one unit time to perform its task (described in (1), (2), and (3) for Com,Ope and Fil, respectively), irrespective of the existence of strings in it. Let I=(w0,{R1,...,Rk},LSF,LFF,{LFF|1≤≤t})be an interpretation to Π. We write C1⇒ C2if there is a transition from C1to C2of I(Π). A configuration C0=({w}, p   ∅,...,∅)with win V∗is called the initial configuration. (We assume that filtering cells are all empty in the initial configuration.) For any n≥0, let C0⇒nCn=(L1,n,...,Lp,n,L(n) out)be a sequence of ntransitions which we call a computation with ntransitions from C0. Then a language L(n) out is called the nth output from C0. Now, we consider two types of computing models induced from I(Π); one is the generating model and the other the accepting model. [Generating Model] In the case of a generating model, we concern all computations whose results are present in the output cell. We define the language generated by I(Π)as follows: LgI(Π) = n≥0 L(n) out, where L(n) out is the nth output from (w0,∅,...,∅)and w0is the axiom of I. [Accepting Model] In the case of an accepting model, we make a slight modification on an interpretation Iand consider the following I=(λ, {R1,...,Rk},LSF, LFF,{LFF|1≤≤t})with LFF which functions in such a way that if a string v filters through LFF, then (not vbut) a special symbol “Yes” is sent to Out. Let wbe an input string to be recognized. Then wis accepted iff the result Yes is present in the output cell after a certain number of transitions from C0=({w},∅,...,∅). Thus, we define the language accepted by I(Π)as follows: LaI(Π) =w∈T∗|Yes ∈L(n) out:thenth output from (w, ∅,...,∅) for some n≥0. Finally, for a class of schemes S={Πof degree (p,k,t)|p,k,t≥0}and for a class of interpretations I, we denote by LMSx(S,I)the family of all languages Lx(I (Π)) specified by those systems as above, where Πis in Sand Iis in I. That is, LMSx(S,I)=Lx(I (Π)) |I∈Iis an interpretation to Π∈S where xis in {a,g}. 4 Characterizations by Membrane Schema Π0 The structure of the membrane computing schema Πintroduced in the previous section seems to be general enough to induce a computing device of the universal computability by finding an appropriate interpretation. In what follows, we will show that such a universal computability can be realized by much simpler schemes together with appropriate interpretations of moderately simple filtering cells. Fig. 2 Membrane computing schema: Π0,k First, we consider the following simple membrane computing schema of degree (2,k,0): Π0,k=(V,T, Com,Ope,Fil,Syn,i s,Out), where: (1) V,T,Ope,isand Out are the same as in Π (2) Com ={Com1,Com2} (3) Fil ={SF,FF}(i.e., SubFil is empty) (4) Syn ={Com1,Opei), (Opei,Com2)|1≤i≤k}∪{(FF,Com1), (Com2,SF), (SF,FF), (FF,Out)}(See (a) of Fig. 2). Let Π0=k≥0Π0,k. We are now in a position to present our first result. Theorem 4.1 There exists a class of interpretations IGsuch that RE =LMSg(Π0, IG). Proof We prove only the inclusion ⊆. (The opposite inclusion is due to a consequence of the Turing–Church thesis.) Let Lbe any language in RE that is generated by a Chomsky type-0 grammar G=(N,T,S,P). Then we consider the following interpretation IG= (S, RG,LSF,LFF)to Π0,k, where (i) For each r:u→vin P, construct Rr={λ→vr, λ →uRr}, and let RG= {Rr|r∈P}. (Note that the cardinality of RGgives kof Π0,k.) (ii) •LSF is given as the following language: Lmir ={xwwRy|x,y,w ∈V∗}. That is, a string filters through SF iff it is an element in Lmir, where V= N∪T∪{r|r∈P}. (Recall that, by definition of SF,anystringinSF is assumed to form a structure, and we assume the hybridization by involution relation ρover V. Specifically, SF performs two functions: it only accepts all structures of molecules containing a single hairpin formed by ww, and then it removes the portion of a hairpin from the structure and sends out the rest part of the string to FF (see (b) of Fig. 2). The structures rejected by SF are all lost.) ing. For example, it is seen that there exists a trade-off between the complexity of network structure in the schema and the complexity of the filtering SF. More specifically, for new terminologies, Lis a star language iff L=F∗for some finite set F. Further, Lis an occurrence checking language iff L=V∗FV∗ for some finite set F. Then it should be noted that in Table 1: (i) LGis a finite union of occurrence checking languages, (ii) Ls,Lrand Lmare star languages, (iii) Lriis a finite intersection of occurrence checking languages and their complements, (iv) Lmiis the complement of an occurrence checking language. Since Π0(or Π1) is more complex than Π2, one may see a trade-off between the complexity of the schema and that of SF, telling that LGfor single (or Lmat for multiple) hairpin checking is simpler than a Dyck language Dfor nested hairpin checking. This kind of trade-off can also be seen in complexity between a series of schemes (Π1,Π1.5,Π2) and the corresponding SFs(Lm,Lmat,D). In this paper, we have just made the first step in the new direction toward understanding and characterizing the nature of the Turing computability from the novel viewpoint of modularity in the membrane computing schema. There seems to remain many left for the future works: •it would be the most interesting to study the relation between the complexity of the language classes and that of SF within a given schema. For instance, we can show that within the schema Π2,CF can be characterized by star (regular) languages for SF. •Instead of insertion operations we adopted in this paper, what kind of operations can be considered for the unique operation in the cells Ope? What kind of different landscape of the computing mechanism can be seen from the new schema? Acknowledgements The first author wishes acknowledge the support of the project TIN200613425 of the Ministerio de Educación y Ciencia of Spain, co-financed by FEDER funds and the support of the project of excellence TIC-581 of the Junta de Andalucía. The second author gratefully acknowledges the support of the Grant of Faculty Development Award, Waseda University and Grant-in-Aid for Scientific Research on Priority Area No. 14085202, Ministry of Education, Culture, Sports, Science, and Technology, Japan. References 1. Cavaliere M, Leupold P (2004) Evolution and observation—a non-standard way to generate formal languages. Theor Comput Sci 321:233–248 2. Cavaliere M, Freund R, Oswald M, Sburlan D (2007) Multiset random context grammars, checkers, and transducers. Theor Comput Sci 372:136–151 3. Chen H, Freund R, Ionescu M, P˘ aun Gh, Pérez-Jiménez MJ (2006) On string languages generated by spiking neural P systems. In: Gutierrez-Naranjo MA, P˘ aun Gh, Riscos-Nunez A, Romero-Campero FJ (eds) Reports on fourth brainstorming week on membrane computing, vol 1, pp 169–193 4. Csuhaj-Varju E, Kari L, P˘ aun Gh (1996) Test tube distributed systems based on splicing. Comput Artif Intell 15(2–3):211–232 5. Dassow J, P˘ aun Gh (1989) Regulated rewriting in formal language theory. Springer, Berlin 6. Freund R, Oswald M (2004) Modeling grammar systems by tissue P systems working in the sequential mode. In: Proceedings of grammar systems workshop, Budapest 7. Ionescu M, P˘ aun Gh, Yokomori T (2006) Spiking neural P systems. Fund Inform 71(2–3):279– 308 8. Margenstern M, Mitrana V, Pérez-Jiménez M (2005) Accepting hybrid networks of evolutionary processors. In: Lecture notes in computer science, vol 3384. Springer, Berlin, pp 235–246 9. Martin-Vide C, Mitrana V, Pérez-Jiménez M, Sancho-Caparrini F (2003) Hybrid networks of evolutionary processors. In: Proceedings of GECCO. Lecture notes in computer science, vol 2723. Springer, Berlin, pp 401–412 10. Martin-Vide C, P˘ aun Gh, Salomaa A (1998) Characterizations of recursively enumerable languages by means of insertion grammars. Theor Comput Sci 205:195–205 11. Martin-Vide C, P˘ aun Gh, Pazos J, Rodriguez-Paton A (2003) Tissue P systems. Theor Comput Sci 296:295–326 12. P˘ aun Gh (1998) Distributed architectures in DNA computing based on splicing: limiting the size of components. In: Calude CS, Casti J, Dinneen MJ (eds) Unconventional models of computation. Springer, Berlin, pp 323–335 13. P˘ aun Gh, Pérez-Jiménez MJ, Yokomori T (2007) Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems. In: Proceedings of DCFS2007, High Tatras, Slovakia, pp. 129–140. Also, to appear in Int J Found Comput Sci, 2008 14. P˘ aun Gh, Rozenberg G, Salomaa A (1998) DNA computing. Springer, Berlin 15. P˘ aun Gh, Sakakibara Y, Yokomori T (2002) P-systems on graph of restricted forms. Publ Math Debrecen 60:635–660 16. Rozenberg G, Salomaa A (1997) Handbook of formal languages. Springer, Berlin