Hybrid Networks of Evolutionary Processors

Hybrid Networks of Evolutionary Processors Carlos Mart´ın-Vide, Victor Mitrana, Mario J. P´erez-Jim´enez, and Fernando Sancho-Caparrini Abstract. A hybrid network of evolutionary processors consists of several processors which are placed in nodes of a virtual graph and can perform one simple operation only on the words existing in that node in accordance with some strategies. Then the words which can pass the output filter of each node navigate simultaneously through the network and enter those nodes whose input filter was passed. We prove that these networks with filters defined by simple random-context conditions, used as language generating devices, are able to generate all linear languages in a very efficient way, as well as non-context-free languages. Then, when using them as computing devices, we present two linear solutions of the Common Algorithmic Problem. 1 Introduction This work is a continuation of the investigation started in [1] and [2] where one has considered a mechanism inspired from cell biology, namely networks of evolutionary processors, that is networks whose nodes are very simple processors able to perform just one type of point mutation (insertion, deletion or substi-tution of a symbol). These nodes are endowed with filters which are defined by some membership or random context condition. Another source of inspiration is a basic architecture for parallel and distributed symbolic processing, related to the Connection Machine [13] as well as the Logic Flow paradigm [6]. This consists of several processors, each of them being placed in a node of a virtual complete graph, which are able to handle data associated with the respective node. Each node processor acts on the local data in accordance with some predefined rules, and, then local data becomes a mobile agent which can navigate in the network following a given protocol. Only such data can be communicated which can pass a filtering process. This filtering process may require to satisfy some conditions imposed by the sending processor, by the receiving processor or by both of them. All the nodes send simultaneously their data and the receiving nodes handle also simultaneously all the arriving messages, according to some strategies, see, e.g., [7,13]. Starting from the premise that data can be given in the form of strings, [4] introduces a concept called network of parallel language processors in the aim of investigating this concept in terms of formal grammars and languages. Networks of language processors are closely related to grammar systems, more specifically to parallel communicating grammar systems [3]. The main idea is that one can place a language generating device (grammar, Lindenmayer system, etc.) in any node of an underlying graph which rewrite the strings existing in the node, then the strings are communicated to the other nodes. Strings can be successfully communicated if they pass some output and input filter. Mechanisms introduced in [1] and [2] simplify as much as possible the networks of parallel language processors defined in [4]. Thus, in each node is placed a very simple processor, called evolutionary processor, which is able to perform a simple rewriting operation only, namely either insertion of a symbol or substitution of a symbol by another, or deletion of a symbol. Furthermore, filters used in [4] are simplified in some versions defined in [1,2]. In spite of these simplifications, these mechanisms are still powerful. In [2] networks with at most six nodes having filters defined by the membership to a regular language condition are able to generate all recursively enumerable languages no matter the underlying structure. This result does not surprise since similar characterizations have been reported in the literature, see, e.g., [5,11,10, 12,14]. Then one considers networks with nodes having filters defined by random context conditions which seem to be closer to the biological possibilities of implementation. Even in this case, rather complex languages like non-context-free ones, can be generated. However, these very simple mechanisms are able to solve hard problems in polynomial time. In [1] it is presented a linear solution for an NP-complete problem, namely the Bounded Post Correspondence Problem, based on networks of evolutionary processors able to substitute a letter at any position in the string but insert or delete a letter in the right end only. This restriction was discarded in [2], but the new variants were still able to solve in linear time another NP- complete problem, namely the “3-colorability problem”. In the present paper, we consider hybrid networks of evolutionary processors in which each deletion or insertion node has its own working mode (at any position, in the left end, or in the right end) and its own way of defining the input and output filter. Thus, in the same network one may co-exist nodes in which deletion is done at any position and nodes in which deletion is done in the right end only. Also the definition of the filters of two nodes, though both are random context ones, may differ. This model may be viewed as a biological computing model in the following way: each node is a cell having a genetic information encoded in DNA sequences which may evolve by local evolutionary events, that is point mutations (insertion, deletion or substitution of a pair of nucleotides). Each node is specialized just for one of these evolutionary operations. Furthermore, the biological data in each node is organized in the form of arbitrarily large multisets of strings (each string appears in an arbitrarily large number of copies), each copy being processed in parallel such that all the possible evolutions events that can take place do actually take place. Definitely, the computational process described here is not exactly an evolutionary process in the Darwinian sense. But the rewriting operations we have considered might be interpreted as mutations and the filtering process might be viewed as a selection process. Recombination is missing but it was asserted that evolutionary and functional relationships between genes can be captured by taking into consideration local mutations only [17]. Furthermore, we were not concerned here with a possible biological implementation, though a matter of great importance. The paper is organized as follows: in the next section we recall the some basic notions from formal language theory and define the hybrid networks of evolutionary processors. Then, we briefly investigate the computational power of these networks as language generating devices. We prove that all regular languages over an n-letter alphabet can be generated in an efficient way by networks having the same underlying structure and show that this result can be extended to linear languages. Furthermore, we provide a non-context-free language which can be generated by such networks. The last section is dedicated to hybrid networks of evolutionary processors viewed as computing (problem solving) devices; we present two linear solutions of the so-called Common Algorithmic Problem. The latter one needs linearly bounded resources (symbols and rules) as well. 2 Preliminaries We start by summarizing the notions used throughout the paper. An alphabet is a finite and nonempty set of symbols. The cardinality of a finite set Ais written card(A). Any sequence of symbols from an alphabet Vis called string (word) over V. The set of all strings over Vis denoted by V∗and the empty string is denoted by ε. The length of a string xis denoted by |x|while the number of occurrences of a letter ain a string xis denoted by |x|a. Furthermore, for each nonempty string xwe denote by alph(x) the minimal alphabet Wsuch that x∈W∗. We say that a rule a→b, with a, b ∈V∪{ε}is a substitution rule if both aand bare not ε;itisadeletion rule if a=εand b=ε;itisaninsertion rule if a=εand b=ε. The set of all substitution, deletion, and insertion rules over an alphabet Vare denoted by SubV,DelV, and InsV, respectively. Given a rule as above σand a string w∈V∗, we define the following actions of σon w: –If σ≡a→b∈SubV, then σ∗(w)=σr(w)=σl(w)={ubv :∃u, v ∈V∗(w=uav)}, {w},otherwise –If σ≡a→ε∈DelV, then σ∗(w)={uv :∃u, v ∈V∗(w=uav)}, {w},otherwise σr(w)={u:w=ua}, {w},otherwise σl(w)={v:w=av}, {w},otherwise –If σ≡ε→a∈InsV, then σ∗(w)={uav :∃u, v ∈V∗(w=uv)},σ r(w)={wa},σ l(w)={aw}. α∈{∗,l,r}expresses the way of applying an evolution rule to a word, namely at any position (α=∗), in the left (α=l), or in the right (α=r) end of the word, respectively. For every rule σ, action α∈{∗,l,r}, and L⊆V∗, we define the α-action of σon Lby σα(L)=w∈Lσα(w). Given a finite set of rules M, we define the α-action of Mon the word wand the language Lby: Mα(w)=  σ∈M σα(w) and Mα(L)=  w∈L Mα(w), respectively. In what follows, we shall refer to the rewriting operations defined above as evolutionary operations since they may be viewed as linguistical formulations of local gene mutations. For two disjoint subsets Pand Fof an alphabet Vand a word over V, we define the predicates ϕ(1)(w;P,F)≡P⊆alph(w)∧F∩alph(w)=∅ ϕ(2)(w;P, F)≡alph(w)⊆P ϕ(3)(w;P, F)≡P⊆alph(w)∧F⊆ alph(w) The construction of these predicates is based on random-context conditions defined by the two sets P(permitting contexts) and F(forbidding contexts). For every language L⊆V∗and β∈{(1),(2),(3)}, we define: ϕβ(L, P, F)={w∈L|ϕβ(w;P,F)}. An evolutionary processor over Vis a tuple (M,PI,FI,PO,FO), where: –Either (M⊆SubV)or(M⊆DelV)or(M⊆InsV). The set Mrepresents the set of evolutionary rules of the processor. As one can see, a processor is “specialized” in one evolutionary operation, only. –PI,FI ⊆Vare the input permitting/forbidding contexts of the processor, while PO,FO ⊆Vare the output permitting/forbidding contexts of the processor. We denote the set of evolutionary processors over Vby EPV. Ahybrid network of evolutionary processors (HNEP for short) is a 7-tuple Γ=(V, G, N, C0,α,β,i 0), where: –Vis an alphabet. –G=(XG,E G) is an undirected graph with the set of vertices XGand the set of edges EG.Gis called the underlying graph of the network. –N:XG−→ EPVis a mapping which associates with each node x∈XGthe evolutionary processor N(x)=(Mx,PI x,FI x,PO x,FO x). –C0:XG−→ 2V∗is a mapping which identifies the initial configuration of the network. It associates a finite set of words with each node of the graph G. –α:XG−→ { ∗ ,l,r};α(x) gives the action mode of the rules of node xon the words existing in that node. –β:XG−→ { (1),(2),(3)}defines the type of the input/output filters of a node. More precisely, for every node, x∈XG, the following filters are defined: input filter: ρx(·)=ϕβ(x)(·;PIx,FI x), output filter: τx(·)=ϕβ(x)(·;POx,FO x). That is, ρx(w) (resp. τx) indicates whether or not the string wcan pass the input (resp. output) filter of x. More generally, ρx(L) (resp. τx(L)) is the set of strings of Lthat can pass the input (resp. output) filter of x. –i0∈XGis the output node of the HNEP. We say that card(XG) is the size of Γ.Ifα(x)=α(y) and β(x)=β(y) for any pair of nodes x, y ∈XG, then the network is said to be homogeneous.In the theory of networks some types of underlying graphs are common, e.g., rings, stars, grids, etc. We shall investigate here networks of evolutionary processors with their underlying graphs having these special forms. Thus a HNEP is said to be a star, ring, or complete HNEP if its underlying graph is a star, ring, grid, or complete graph, respectively. The star, ring, and complete graph with nvertices is denoted by Sn,Rn, and Kn, respectively. Aconfiguration of a HNEP Γas above is a mapping C:XG−→ 2V∗which associates a set of strings with every node of the graph. A configuration may be understood as the sets of strings which are present in any node at a given moment. A configuration can change either by an evolutionary step or by a communication step. When changing by an evolutionary step, each component C(x) of the configuration Cis changed in accordance with the set of evolutionary rules Mxassociated with the node xand the way of applying these rules α(x). Formally, we say that the configuration Cis obtained in one evolutionary step from the configuration C, written as C=⇒C,iff C(x)=Mα(x) x(C(x)) for all x∈XG. When changing by a communication step, each node processor x∈XGsends one copy of each string it has, which is able to pass the output filter of x,toall the node processors connected to xand receives all the strings sent by any node processor connected with xproviding that they can pass its input filter. Formally, we say that the configuration Cis obtained in one communication step from configuration C, written as CC,iff C(x)=(C(x)−τx(C(x))) ∪ {x,y}∈EG (τy(C(y)) ∩ρx(C(y))) for all x∈XG. Let Γan HNEP, the computation in Γis a sequence of configurations C0,C 1,C 2,..., where C0is the initial configuration of Γ,C2i=⇒C2i+1 and C2i+1 C2i+2, for all i≥0. By the previous definitions, each configuration Ciis uniquely determined by the configuration Ci−1. If the sequence is finite, we have a finite computation. If one uses HNEPs as language generating devices, then the result of any finite or infinite computation is a language which is collected in the output node of the network. For any computation C0,C 1,..., all strings existing in the output node at some step belong to the language generated by the network. Formally, the language generated by Γis L(Γ)=s≥0Cs(i0). The time complexity of computing a finite set of strings Zis the minimal number ssuch that Z⊆s t=0 Ct(i0). 3 Computational Power of HNEP as Language Generating Devices First, we compare these devices with the simplest generative grammars in the Chomsky hierarchy. In [2], one proves that the families of regular and context-free languages are incomparable with the family of languages generated by homogeneous networks of evolutionary processors. HNEPs are more powerful, namely Theorem 1. Any regular language can be generated by any type (star, ring, complete) of HNEP. Proof. Let A=(Q, V, δ, q0,F) be a deterministic finite automaton; without loss of generality we may assume that δ(q,a)=q0holds for each q∈Qand each a∈V. Furthermore, we assume that card(V)=n. We construct the following complete HNEP (the proof for the other underlying structures is left to the reader): Γ=(U, K2n+3,N,C 0,α,β,f). The alphabet Uis defined by U=V∪V∪Q∪{sa|s∈Q, a ∈V},where V={a|a∈V}. The set of nodes of the complete underlying graph is {x0,x 1,x f}∪V∪V, and the other parameters are given in Table 1, where sand bare generic states from Qand symbols from V, respectively. One can easily prove by induction that 1. δ(q,x)∈Ffor some q∈Q\{q0}if and only if xq ∈C8|x|(0). 2. xis accepted by A(x∈L(A)) if and only if x∈Cp(f) for any p≥8|x|+1. Therefore, L(A) is exactly the language generated by Γ. Table 1. Node MPI FI PO FO C0α β x0{q→sb}δ(s,b)=q∅ {sb}s,b ∪{b}b∅ ∅ F∗(1) a∈V ε →a{sa}s∪V Q U ∅ ∅ l(2) a∈V{sa→s}s{a}Q∅ ∅ ∅ ∗ (1) x1{b→b}b∅ {sb}s,b ∅ ∅ ∅ ∗ (1) xfq0→ε{q0}V∅V∅r(1) Surprisingly enough, the size of the above HNEP, hence its underlying structure, does not depend on the number of states of the given automaton. In other words, this structure is common to all regular languages over the same alphabet, no matter the state complexity of the automata recognizing them. Furthermore, all strings of the same length are generated simultaneously. Since each linear grammar can be transformed into an equivalent linear grammar with rules of the form A→aB, A →Ba,A →εonly, the proof of the above theorem can be adapted for proving the next result. Theorem 2. Any linear language can be generated by any type of HNEP. We do not know whether these networks are able to generate all context-free languages, but they can generate non-context-free languages as shown below. Theorem 3. There are non-context-free languages that can be generated by any type of HNEP. Proof. We construct the following complete HNEP which generates the noncontext-free language L={wcx |x∈{a, b}∗,w is a permutation of x}: Γ=(V,K9,N,C 0,α,β,y 2), where V={a, b, a,b ,X a,X b,X},X K9={y0,y 1,y 2,y a,y b,¯ya,¯yb,˜ya,˜yb},and the other parameters are given in Table 2, where uis a generic symbol in {a, b}. The working mode of this network is rather simple. In the node y0there are generated strings of the form Xnfor any n≥1. They can leave this node as soon as they receive a Dat their right end, the only node able to receive them being y1.Iny1, either Xaor Xbis added to their right end. Thus, for a given n, the strings XnDXaand XnDXbare produced in y1. Let us follow what happens with the strings XnDXa, a similar analysis applies to the strings XnDXbas well. So, XnDXagoes to yawhere any occurrence of Xis replaced by ain different identical copies of XnDXa. In other words, yaproduces each string XkaXn−k−1DXa,0≤k≤n−1. All these strings are sent out but no node, except ¯ya, can receive them. Here, Xais replaced by aand the obtained strings are sent to ˜yawhere ais substituted to a. As long as the strings contains occurrences of X, they follow the same itinerary, namely y1,y u,¯yu,˜yu,u∈{a, b}, depending on what symbol Xaor Xbis added in y1. After a finite number of such cycles, when no occurrence of Xis present in the strings, they are received by y2where Dis replaced by cin all of them, and Table 2. Node MPI FI PO FO C0α β y0{ε→X, ε →D} ∅ {a,b ,a,b,X a,X b} {D} ∅ {ε}r(1) y1{ε→Xa,ε→Xb} ∅ {Xa,X b,a ,b } ∅ ∅ ∅ r(1) yu{X→u} {Xu} {a,b } ∅ ∅ ∅ ∗ (1) ¯yu{Xu→u} {u} ∅ ∅ ∅ ∅ ∗ (1) ˜yu{u→u} {u} {Xa,X b} ∅ ∅ ∅ ∗ (1) y2{D→c} ∅ {X, a,b ,X a,X b} ∅ {a, b} ∅ ∗ (1) they remain in this node for ever. By these explanations, the node y2collects all strings of Land any string which arrives in this node belongs to L. A more precise characterization of the family of languages generated by HNEPs remains to be done. 4 Solving Problems with HNEPs HNEPs may be used for solving problems in the following way. For any instance of the problem the computation in the associated HNEP must be finite. In particular, this means that there is no node processor specialized in insertions. If the problem is a decision problem, then at the end of the computation, the output node provides all solutions of the problem encoded by strings, if any, otherwise this node will never contain any word. If the problem requires a finite set of words, this set will be in the output node at the end of the computation. In other cases, the result is collected by specific methods which will be indicated for each problem. In [2] one provides a complete homogeneous NEP of size 7m+2 which solves in O(m+n) time an (n, m)–instance of the “3-colorability problem” with n vertices and medges. In the sequel, following the descriptive format for three NP-complete problems presented in [9] we present a solution to the Common Algorithmic Problem. The three problems are: 1. The maximum independent set: Given an undirected graph G=(X, E), where Xis the finite set of vertices and Eis the set of edges given as a family of sets of two vertices, find the cardinality of a maximal subset (with respect to inclusion) of Xwhich does not contain both vertices connected by any edge in E. 2. The vertex cover problem: Given an undirected graph find the cardinality of a minimal set of vertices such that each edge has at least one of its extremes in this set. 3. The satisfiability problem: For a given set Pof Boolean variables and a finite set Uof clauses over P, does a truth assignment for the variables of Pexist satisfying all the clauses of U? For detailed formulations and discussions about their solutions, the reader is referred to [8]. These problems can be viewed as special cases of the following algorithmic problem, called the Common Algorithmic Problem (CAP) in [9]: let Sbe a finite set and Fbe a non-empty family of subsets of S. Find the cardinality of a maximal subset of Swhich does not include any set belonging to F. The sets in Fare called forbidden sets. We say that (F,S)isan(card(S), card(F))–instance of CAP Let us show how the three problems mentioned above can be obtained as special cases of CAP. For the first problem, we just take S=Xand F=E. The second problem is obtained by letting S=Xand Fcontains all sets o(x)= {x}∪{y∈X|{x, y}∈E}. The cardinality one looks for is the difference between the cardinality of Sand the solution of the CAP. The third problem is obtained by letting S=P∪P, where P={p|p∈P}, and F={F(C)|C∈U}, where each set F(C) associated with the clause Cis defined by F(C)={p|pappears in C}∪{p|¬pappears in C}. From this it follows that the given instance of the satisfiability problem has a solution if and only if the solution of the constructed instance of the CAP is exactly the cardinality of P. First, we present a solution of the CAP based on homogeneous HNEPs. Theorem 4. Let (S={a1,a 2,...,a n},F ={F1,F 2,...,F m}),bean(n, m)– instance of the CAP. It can be solved by a complete homogeneous HNEP of size m+2n+2in O(m+n) time. Proof. We construct the complete homogeneous HNEP Γ=(U, Km+2n+2,N,C 0,α,β). Since the result will be collected in a way which will be specified later, the output node is missing. The alphabet of the network is U=S∪¯ S∪S∪{Y,Y1,Y 2,...,Y m+1}∪{b}∪{Z0,Z 1,...,Z n}∪ {Y 1,Y 2,...,Y m+1}∪{X1,X 2,...,X n}, where ¯ Sand Sare copies of Sobtained by taking the barred and primed copies of all letters from S, respectively. The nodes of the underlying graph are: x0,x F1,x F2,...,x Fm,x a1,x a2,...,x an,y 0,y 1,...,y n. The mapping Nis defined by: N(x0)=({Xi→ai,X i→¯ai|1≤i≤n}∪{Y→Y1}∪{Y i→Yi+1 | 1≤i≤m},{Y i|1≤i≤m},∅,∅,{Xi|1≤i≤n}∪{Y}), N(xFi)=({¯a→a|a∈Fi},{Yi},∅,∅,∅),for all 1 ≤i≤m, N(xaj)=({a j→¯aj}∪{Yi→Y i|1≤i≤m},{a j},∅,∅,{a j}∪{Yi| 1≤i≤m}),for all 1 ≤j≤n, N(yn)=({¯ai→b|1≤i≤n}∪{Ym+1 →Z0},{Ym+1},∅,{Z0,b},¯ S), N(yn−i)=({b→Zi},{Zi−1},∅,{b, Zi},∅),for all 1 ≤i≤n.