Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques

Solving the ST-Connectivity Problem with Pure Membrane Computing Techniques Zsolt Gazdag1, Miguel A. Guti´errez–Naranjo2 1Department of Algorithmics and their Applications Faculty of Informatics E¨otv¨os Lor´and University, Hungary [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012, Spain [email protected] Summary. In Membrane Computing, the solution of a decision problem Xbelonging to the complexity class Pvia a polynomially uniform family of recognizer P systems is trivial, since the polynomial encoding of the input can involve the solution of the problem. The design of such solution has one membrane, two objects, two rules and one computation step. Stricto sensu, it is a solution in the framework of Membrane Computing, but it does not use Membrane Computing strategies. In this paper, we present three designs of uniform families of P systems that solve the decision problem STCON by using Membrane Computing strategies (pure Membrane Computing techniques): P systems with membrane creation, P systems with active membranes with dissolution and without polarizations and P systems with active membranes without dissolution and with polarizations. Since STCON is NL-complete, such designs are constructive proofs of the belonging of NL to PMCMC ,PMCAM0 +dand PMCAM+ −d. 1 Introduction Membrane Computing [13] is a well-established model of computation inspired by the structure and functioning of cells as living organisms able to process and generate information. It starts from the assumption that the processes taking place in the compartmental structures as living cells can be interpreted as computations. The devices of this model are called P systems. Among the different research lines in Membrane Computing, one of the most vivid is the search of frontiers between complexity classes of decision problems, i.e., to identify collections of problems that can be solved (or languages that can be decided) by families of P systems with similar computational resources. In order to settle the correspondence between complexity classes and P system families, 208 Z. Gazdag and M.A. Guti´errez–Naranjo recognizer P systems were introduced in [9, 10]. Since then, recognizer P systems are the natural framework to study and solve decision problems within Membrane Computing. In the last years, many papers have been published about the problem of deciding if a uniform family of recognizer P systems of type Fbuilt in polynomial time is able to solve the decision problem X. This is usually written as the problem of deciding if Xbelongs to PMCFor not. It has been studied for many P system models Fand for many decision problems X(see, e.g., [2, 3, 4, 5] and references therein). The solution of a decision problem Xbelonging to the complexity class P via a polynomially uniform family of recognizer P systems is trivial1, since the polynomial encoding of the input can involve the solution of the problem. On the one hand, by definition, X∈Pif there exists a deterministic algorithm A working in polynomial time that solves X. On the other hand, the belonging of X to PMCFrequires a polynomial time mapping cod that encodes the instances u of the problem Xas multisets wich will be provided as inputs. Formally, given a decision problem Xand an algorithm Aas described above, two different functions s(size) and cod (encoding) can be defined for each instance uof the decision problem: •s(u) = 1, for all u •cod(u) = {yes if A(u) = yes no if A(u) = no. The family of P systems which solves Xis Π={Π(n)}n∈Nwith Π(n) = ⟨Γ, Σ, H, µ,w, R, i⟩ •Alphabet: Γ={yes, no} •Input alphabet: Σ=Γ •Set of labels: H={skin} •Membrane structure: [ ]skin •Initial multisets: w=∅ •Input label: i=skin •Set of rules: [yes ]skin →yes [ ]skin and [ no ]skin →no [ ]skin. Both are send-out rules. Trivially, for all instance uof the problem, Π(s(u)) + cod(u) provides the right solution in one computation step. Stricto sensu, it is a solution in the framework of Membrane Computing, but it does not use Membrane Computing strategies. All the work is done in the algorithm Aand one can wonder if the computation itself can be performed by using pure Membrane Computing techniques. We focus now on the well-known ST-Connectivity problem (known as STCON). It can be settled as follows: Given a directed graph ⟨V, E⟩and two 1See [8, 11]. Solving the ST-Connectivity Problem . . . 209 vertex sand tin V, the STCON problem consists on deciding if tis reachable from s, i.e., if there exists a sequence of adjacent vertices (i.e., a path) which starts with sand ends with t.It is known that it is an NL-complete problem, i.e., it can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space and every problem in the class NL is reducible to STCON under a log-space reduction. In this paper, we study the STCON in the framework of P systems. As shown above, since STCON ∈NL ⊆P, there exist a trivial family of P systems in PMCFwhich solves it, regardless the model F. It suffices that Fdeals with send-out rules. In this paper, we present three designs of uniform families of P systems that solve the decision problem STCON by pure Membrane Computing techniques, i.e., techniques where the features of the model Fare exploited in the computation: P systems with membrane creation, P systems with active membranes with dissolution and without polarizations and P systems with active membranes without dissolution and with polarizations. We provide such designs and show the differences with previous studies found in the literature. Since STCON is NL-complete, such designs are constructive proofs of the belonging of NL to PMCMC,PMCAM0 +dand PMCAM+ −d. The paper is structured as follows: First of all, we recall some basic definitions used along the paper. In Section 3, previous works on NL are revisited. Next, our designs of solutions are provided and the paper finishes with some conclusions and presenting research lines for a future work. 2 Preliminaries Next, some basic concepts used along the paper are recalled. We assume that the reader is familiar with Membrane Computing techniques (for a detailed description, see [13]). A decision problem, X, is a pair (IX, θX) such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total Boolean function over IX. A P system with input is a tuple (Π, Σ, iΠ), where Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets M1, . . . , Mpassociated with them; Σis an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and iΠis the label of a distinguished (input) membrane. Let (Π, Σ, iΠ) be a P system with input, Γbe the working alphabet of Π,µits membrane structure, and M1, . . . , Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of (Π, Σ, iΠ)with input mis (µ, M1, . . . , MiΠ∪m, . . . , Mp). We denote by IΠthe set of all inputs of the P system Π(i.e. IΠis a collection of multisets over Σ). In the case of P systems with input and with external output, the above concepts are introduced in a similar way. Definition 1. Arecognizer P system is a P system with input, (Π, Σ, iΠ), and with external output such that: 210 Z. Gazdag and M.A. Guti´errez–Naranjo 1. The working alphabet contains two distinguished elements yes,no. 2. All its computations halt. 3. If Cis a computation of Π, then either some object yes or some object no (but not both) must have been released into the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the external environment associated to the corresponding halting configuration of C. 3 Previous Works The relation between the complexity class NL and Membrane Computing models has already been explored in the literature. In [6], Murphy and Woods claim that NL ⊆PMCAM0 −d,−u, i.e., every problem in the complexity class NL can be solved by a non-uniform family of recognizer P systems with active membranes without polarization and without dissolution. The proof shows the design of a family of P systems with active membranes without polarization and without dissolution which solves STCON and considers the NL-completeness of STCON. Nonetheless, the authors use a non standard definition of recognizer P systems. According to the usual definition of recognizer P system (see, e.g., [4]), either one object yes or one object no (but no both) must have been released into the environment, and only in the last step of the computation. In the proposed family by Murphy and Woods, it is easy to find a P system which sends yes to the environment in an intermediate step of the computation and sends no to the environment in the last step of the computation, so their proof of NL ⊆PMCAM0 −d,−ucannot be considered valid with respect to the standard definition of recognizer P systems. Counterexample: Let us consider the instance (s, t, G) of STCON where G has only two vertices sand tand only one edge (s, t). According to [6], the P system of the cited model that solves this instance has Γ={s, t, yes, no, c0, . . . , c4}as alphabet, has unique label and [ ]has membrane structure. The initial configuration is [s c4]hand the set of rules consists of the following seven rules: [s→t]h[t]h→[ ]hyes [c0]h→[ ]hno [ci→ci−1]hfor i∈ {1, . . . , 4}. It easy to check that this P system sends yes to the environment in the second step of computation and sends no in the fifth (and last) step, so, according to the standard definition, it is not a recognizer P system. In [7] Murphy and Woods revisited the solution of STCON by non-uniform families of recognizer P systems and considered three different ways of the acceptance in recognizer P systems, one of them was the standard one (Def. 1). Solving the ST-Connectivity Problem . . . 211 4 Three Designs for the STCON Problem In this section, we provide three uniform families of P systems that solve the STCON problem in three different P system models. All these models use the same encoding for an instance of the problem. We do not loss generality if we consider the nvertices of the graph as {1, . . . , n}. In this case, a concrete instance I= (s, t, ⟨V, E⟩) of the STCON on a graph ⟨V, E⟩with vertices {1, . . . , n}, can be encoded as cod(I) = {xs, yt} ∪ {aij : (i, j)∈E}, i.e., xsstands for the starting vertex, ytfor the ending vertex and aij for each edge (i, j) in the graph. By using this coding, all the instances of the STCON problem with nvariables, can be encoded with the alphabet Σ={xi:i∈ {1, . . . , n}} ∪ {yj:j∈ {1, . . . , n}} ∪ {aij :i, j ∈ {1, . . . , n}} whose cardinality is 2n+n2. Next we present three solutions of the STCON problem by P systems. The first two solutions are based on P systems with active membranes, the last one uses P systems with membrane creation. The first solution does not use membrane dissolution but uses the polarizations of the membranes. The second solution does not use polarizations but uses membrane dissolution instead. Moreover, none of these solutions use membrane division rules. All the three solutions, roughly speaking, work in the following way. For a given directed graph G= (V, E) and vertices sand t, the system creates/activates certain membranes in the initial configuration corresponding to the edges in E. Then, these membranes will be used to create those objects that represent the vertices reachable from s. Meanwhile, it is tested whether or not the vertex tis created or not. If yes, the system initiates a process which will send yes out to the environment. If the vertex tis not produced by the system, i.e., tis not reachable from sin G, then a counter will create the symbol no which is then sent out to the environment. 4.1 P Systems with Active Membranes, with Polarization and without Dissolution As a first approach, we will provide the design of a uniform family Π={Πn}n∈N of P systems in PMCAM−dwhich solves STCON. Each P system Πnof the family decides on all the possible instances of the STCON problem on a graph with nnodes. Such P systems use two polarizations, but they do not use division or dissolution rules, so not all the types of rules of P systems with active membranes are necessary to solve STCON. Each Πnwill receive as input an instance of the STCON as described above and will release yes or no into the environment in the 212 Z. Gazdag and M.A. Guti´errez–Naranjo last step of the computation as the answer of the decision problem. The family presented here is Πn=⟨Γn, Σn, Hn, ECn, µn, wa n, w1 n, . . . , wn n, w11 n, . . . , wnn n, wskin n,Rn, in⟩. For the sake of simplicity, thereafter we will omit the subindex n. •Alphabet: Γ={xi, yi, ti:i∈ {1, . . . , n}} ∪ {aij, zij :i, j ∈ {1, . . . , n}}∪ {ci:i∈ {0, . . . , 3n+ 1}}∪ {k, yes, no}. •Input alphabet: Σ, as described at the beginning of the section. Let us remark that Σ⊂Γ. •Set of labels: H={⟨i, j⟩:i, j ∈ {1, . . . , n}} ∪ {1, . . . , n}∪{a, skin}. •Electrical charges: EC ={0,+}. •Membrane structure: [ [ ]0 1...[ ]0 n[ ]0 ⟨1,1⟩. . . [ ]0 ⟨n,n⟩[ ]0 a]0 skin. •Initial multisets: wa=c0,wskin =wij =wk=λfor i, j, k ∈ {1, . . . , n}. •Input label: i=skin. The set of rules R: R1. aij [ ]0 ⟨i,j⟩→[aij ]+ ⟨i,j⟩for i, j ∈ {1, . . . , n}. Each input object aij activates the corresponding membrane by changing its polarization. Notice that such a symbol aij represents an edge in the input graph. R2. yj[ ]0 j→[yj]+ jfor j∈ {1, . . . , n}. The object yjactivates the membrane jby changing its polarization. As the input multiset always has exactly one object of the form yj,Πnwill have a unique membrane with label in {1, . . . , n}and polarization +. R3.[xi→zi1. . . zinti]0 skin for i∈ {1, . . . , n}. The goal of these rules is to create n+ 1 copies of an object xi. A copy zij will be able to produce an object xjif the edge (i, j) belongs to E. The object tiwill be used to witness that vertex iis reachable. R4. zij [ ]+ ⟨i,j⟩→[xj]0 ⟨i,j⟩ tj[ ]+ j→[k]0 j}for i, j ∈ {1, . . . , n}. If the membrane with label ⟨i, j⟩has polarization +, then the symbol zij produces a symbol xjinside this membrane. Meanwhile, the polarization of this membrane changes from + to 0, i.e., the membrane is deactivated. Moreover, if the symbol tjappears in the skin and the membrane with label jhas positive polarization, then an object kis produced inside this membrane. Such object kwill start the process to send yes out to the environment. R5.[k]0 j→k[ ]0 jk[ ]0 a→[k]+ a. The object kis a witness of the success of the STCON problem. If it is produced, it goes into the membrane with label aand changes its polarization to +. R6.[xj]0 ⟨i,j⟩→xj[ ]0 ⟨i,j⟩for i, j ∈ {1, . . . , n}. Solving the ST-Connectivity Problem . . . 213 The produced object xjis sent to the membrane skin in order to go on the computation by rules form R3. R7.[ci→ci+1]0 a[c3n+1]0 a→no [ ]0 a [ci→ci+1]+ a[c3n+1]+ a→yes [ ]0 a}for i∈ {0, . . . , 3n}. Object cievolves to ci+1 regardless of the polarization of the membrane a. If during the evolution the object khas gone inside such membrane, then the polarization changes to + and the object c3n+1 will produce yes in the membrane skin. Otherwise, if the object kis not produced, the polarization is not changed and the object c3n+1 will produce no. R8.[no]skin →no [ ]skin [yes]skin →yes [ ]skin . Finally, yes or no is sent out the P system in the last step of computation. To see in more details how the computation of the presented P system goes, let us consider an instance I= (s, t, G) of STCON where Gis a graph ⟨{1, . . . , n}, E⟩. The computation of Πnon cod(I) can be described as follows. During the first step, using rules in R1, every aij enters to the membrane with label ⟨i, j⟩and changes its polarization to +. Thus, after the first step the edges in Eare encoded by the positive polarizations of the membranes with labels of the form ⟨i, j⟩. During the same step, using the corresponding rule in R2,ytenters to the membrane with label tand changes its polarization to +. This membrane will be used to recognize if an object representing that tis reachable from sis introduced by the system. Now let l∈ {1,4, . . . , 3(n−1) + 1}and consider an object xiin the skin membrane. During the lth step, using rules in R3,xicreates n+ 1 copies of itself. The system will try to use a copy zij (j∈ {1, . . . , n}) in the next step to create a new object xj. The copy tiwill be used to decide if i=t. During the (l+ 1)th step, using rules in R4, the systems sends zij into the membrane with label ⟨i, j⟩if that membrane has a positive polarization. Meanwhile, zij evolves to xjand the polarization of the membrane changes to neutral. During the same step, if i=tand the membrane with label thas positive polarization, then the system sends tito this membrane. Meanwhile, tievolves to kand the polarization of membrane tchanges to neutral. During the (l+ 2)th step, using rules in R6, the object xjis sent out from the membrane with label ⟨i, j⟩. Moreover, if the membrane with label tcontains k, then this kis sent out from membrane t. One can see that during the above three steps the system introduces an object xjif and only if (i, j) is an edge in E. Using this observation we can derive that during the computation of the system, an object xjappears in the skin if and only if there is a path in Gfrom sto j. Thus, tis reachable from sin Gif and only if there is a configuration of Πnwhere the skin contains xt. However, in this case an object kis introduced in the membrane with label t. It can also be seen that Πnsends out to the environment yes if and only if kappears in membrane t. Moreover, if kdoes not appear in membrane t, then the systems sends out to the environment no. Thus, Πnsends out to the environment yes or no according to that tis reachable from sor not. As Πnstops in at most 3n+ 2 steps, we 214 Z. Gazdag and M.A. Guti´errez–Naranjo can conclude that the family Πdecides STCON in linear time in the number of vertices of the input graph. 4.2 P Systems with Active Membranes, with Dissolution and without Polarization Based on the solution presented in the previous sub-section, we give here a uniform family Π={Πn}n∈Nin PMCAM0which solves STCON. As here we cannot use the polarizations of the membranes, we use membrane dissolution to select those membranes of the initial configuration that correspond to the edges of the input graph. Next we will describe the mentioned family Π. Since we do not use polarizations, we do not indicate it at the upper-right corner of the membranes. The family presented here is Πn=⟨Γ, Σ, H, EC, µ, W, R, i⟩. •Alphabet: Γ={xi, v1i, v2i, v3i, vi, yi, ti:i∈ {1, . . . , n}} ∪ {aij, zij :i, j ∈ {1, . . . , n}}∪ {ci:i∈ {0, . . . , 3n+ 4}}∪ {k, yes, no}. •Input alphabet: Σ, as described at the beginning of the section. •Set of labels: H={⟨i, j, in⟩,⟨i, j, out⟩:i, j ∈ {1, . . . , n}} ∪ {⟨i, in⟩,⟨i, out⟩: i∈ {1, . . . , n} ∪ {a, skin}. •Electrical charges: EC =∅. •Membrane structure: [ [[ ]⟨1,in⟩]⟨1,out⟩. . . [[ ]⟨n,in⟩]⟨n,out⟩[[ ]⟨1,1,in⟩]⟨1,1,out⟩. . . [[ ]⟨n,n,in⟩]⟨n,n,out⟩[ ]a]skin. •Initial multisets: W={wa, w⟨1,in⟩, . . . , w⟨n,in⟩, w⟨1,out⟩, . . . , w⟨n,out⟩, w⟨1,1,in⟩, . . . , w⟨n,n,in⟩, w⟨1,1,out⟩, . . . , w⟨n,n,out⟩, wskin}, where wa=c0,wskin =w⟨i,j,out⟩=w⟨k,out⟩=λ,w⟨i,j,in⟩=w⟨k,in⟩=f0, for i, j, k ∈ {1, . . . , n}. •Input label: i=skin. The set of rules R: R0.[xi→v1i]skin,[vji →vj+1,i]skin,[v3i→vi]skin for i∈ {1, . . . , n}and j∈ {1,2}. In this solution we cannot use the objects xiin the same role as we did in the previous sub-section because of the following reason. The system needs four steps to select those membranes in the initial membrane configuration that correspond to the edges in E. Thus, the system introduces in four steps the objects viwhich will act in this solution as the objects xidid in the previous one. R1.[fm→fm+1]⟨i,j,in⟩ [f3]⟨i,j,in⟩→f4 [f4]⟨i,j,out⟩→f4    for i, j ∈ {1, . . . , n},m∈ {0,1,2}. Solving the ST-Connectivity Problem . . . 215 These rules dissolve the membranes with label ⟨i, j, in⟩and ⟨i, j, out⟩if the input symbol aij is not present in the system. On the other hand, if aij is in the system, then it prevents the dissolution of the membrane with label ⟨i, j, out⟩using the following rules. R2. aij [ ]⟨i,j,m⟩→[aij]⟨i,j,m⟩ [aij]⟨i,j,in⟩→aij }for i, j ∈ {1, . . . , n},m∈ {in, out}. By these rules the input symbol aij goes into the membrane with label ⟨i, j, in⟩ and dissolves that. This way the second rule in R1 cannot be applied, thus the membrane with label ⟨i, j, out⟩cannot be dissolved by the third rule. R3.[fm→fm+1]⟨j,in⟩ [f3]⟨j,in⟩→f4 [f4]⟨j,out⟩→f4    for j∈ {1, . . . , n},m∈ {0,1,2}. These rules dissolve the membranes with label ⟨j, in⟩and ⟨j, out⟩if the input symbol yjis not present in the system. However, if yjis in the system, then it prevents the dissolution of the membrane with label ⟨j, out⟩using the following rules. R4. yj[ ]⟨j,m⟩→[yj]⟨j,m⟩ [yj]⟨j,in⟩→yj}for j∈ {1, . . . , n}and m∈ {in, out}. By these rules the input symbol yjgoes into the membrane with label ⟨j, in⟩and dissolves that. With this it is achieved that the membrane with label ⟨j, out⟩is not dissolved by the rules in R3. R5.[vi→zi1. . . zinti]skin for i∈ {1, . . . , n}. The role of these rules is the same as that of the rules in R3 in Section 4.1. R6. zij [ ]⟨i,j,out⟩→[vj]⟨i,j,out⟩ tj[ ]⟨j,out⟩→[k]⟨j,out⟩}for i, j ∈ {1, . . . , n}. The role of these rules is similar to that of the rules in R4 in Section 4.1: If the membrane with label ⟨i, j, out⟩has not been dissolved, then the object zij produces a symbol vjinside this membrane. Analogously, if the symbol tjappears in the skin and the membrane with label ⟨j, out⟩is not dissolved, then an object kis produced inside this membrane. Such object kwill start the process to send yes out to the environment. R7.[k]⟨j,out⟩→k[ ]⟨j,out⟩k[ ]a→[k]a[k]a→k. The object kis a witness of the success of the STCON problem. If it is produced, it goes into the membrane with label aand dissolves it. R8.[vj]⟨i,j⟩→vjfor i, j ∈ {1, . . . , n}. The produced object vjdissolves the membrane with label ⟨i, j⟩as the computation does not need any more this membranes. This way the object vjgets to the skin and the computation can go on using the rules in R5. R9.[ci→ci+1]a[c3n+4]a→no [ ]a [ci+1]skin →[yes]skin }for i∈ {0, . . . , 3n+ 3}. Object cievolves to ci+1 in membrane with label a. If during the evolution the object khas gone inside this membrane, then it dissolves it and the object ci+1 gets to the membrane swhere it produces yes. Otherwise, if the object kis not produced, c3n+4 remains in membrane with label aand produces no.