P Systems with Membrane Creation and Rule Input

P Systems with Membrane Creation and Rule Input Miguel Angel Guti´errez-Naranjo, Mario J. P´erez-Jim´enez 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: {magutier, marper}@us.es Summary. When a uniform family of recognizer P systems is designed to solve a problem, the data of a concrete instance of the problem is usually provided via a multiset which is placed in the so-called input membrane. In this paper we present a new definition for recognizer P systems, called with rule input, where the data of the instance is provided via a set of rules which are introduced in the system at the beginning of the computation. We also discuss a new semantic for P systems with membrane creation and, as an example, a uniform family of recognizer P systems with rule input which solves the Subset Sum problem is provided. 1 Introduction Solving NP-complete problems is done in the membrane computing framework by generating an exponential amount of workspace in polynomial time and using the parallelism to check simultaneously all the candidate solutions. The way in which this exponential number of membranes is created in polynomial time is based on biological processes inspired in living cells. Basically, two processes are used in order to produce new membranes: mitosis (membrane division) and autopoiesis (membrane creation), see [?]. Both ways of generating new membranes have given rise to different variants of P systems: P systems with active membranes, where the workspace is generated by membrane division, and P systems with membrane creation, where the new membranes are created from objects. Both models are universal from a computational point of view, but technically, they are pretty different. In fact, nowadays there does not exist any 2 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez theoretical result which proves that these models can simulate each other in polynomial time. P systems with active membranes have been successfully used to design solutions to well-known NP-complete problems, as SAT [?], Subset Sum [?], Knapsack [?], Bin Packing [?] and Partition [?], but as Gh. P˘aun pointed in [?]“membrane division was much more carefully investigated than membrane creation as a way to obtain tractable solutions to hard problems”. Recently, the first results related to the power and design of algorithms to solve NP problems by means of P systems using membrane creation have arisen (see [?,?,?]). In these solutions, both in the model of P systems with active membranes and P systems with membrane creation, a uniform family of recognizer P systems is designed to solve the problem and the data of a concrete instance of the problem is usually provided via a multiset which is placed in the socalled input membrane. In this paper we present a new definition for recognizer P systems with rule input, where the data of the instance is provided via a new set of rules. We also discuss a new semantics for P systems with membrane creation and, as an example, a uniform family of recognizer P systems with rule input which solves the Subset Sum problem is provided. The paper is organized as follows. P systems with membrane creation are remembered in the next section, together with a short disscusion about their semantics. In section 3 recognizer P systems with input rules are presented. As an example, a uniform family of recognizer P systems with rule input which solves the Subset Sum problem is presented in Section 4. Finally, some formal details and conclusions are given in the last sections. 2 A new semantics for P systems with membrane creation Since Gh. P˘aun presented the cellular computation with membranes, many different variants have been proposed. If the membrane structure is considered to set a classification among these different variants, two big groups are obtained: P systems where the initial structure does not change along computations and P systems where the tree structure of the membranes vary (or can do it) along computation. The decrease of the number of membranes is made by applying the so-called dissolution rules, of the form [a]e→b, where the object ainside a membrane with label eproduces the dissolution of the membrane, the object adisappears and a new element band the rest of the multiset in the membrane go to its father (more precisely, they go to the P Systems with Membrane Creation and Rule Input 3 closest non-dissolved ancestor in the membrane hierarchy, since several membranes can dissolve in the same step). Increasing the number of membranes are usually made via division of existing ones or creating new membranes from objects1. We recall that a P system with membrane creation is a construct of the form Π= (O, H, µ, w1,...,wm, R), where: 1. m≥1 is the initial degree of the system; 2. Ois the alphabet of objects; 3. His a finite set of labels for membranes; 4. µis a membrane structure consisting of mmembranes labelled (not necessarily in a one-to-one manner) with elements of H; 5. w1,...,wmare strings over O, describing the multisets of objects placed in the mregions of µ; 6. Ris a finite set of rules, of the following forms: a) [a→v]h, where h∈H,a∈O, and vis a string over Odescribing a multiset of objects. These are object evolution rules associated with membranes and depending only on the label of the membrane. b) a[ ]h→[b]h, where h∈H,a, b ∈O. These are send-in communication rules. An object is introduced in the membrane, possibly modified during the process. c) [a]h→[ ]hb, where h∈H,a, b ∈O. These are send-out communication rules. An object is sent out of the membrane, possibly modified during the process. d) [a]h→b, where h∈H,a, b ∈O. These are dissolution rules. In reaction with an object, a membrane is dissolved, while the object specified in the rule can be modified. e) [a→[v]h2]h1, where h1, h2∈H,a∈O, and vis a string over O describing a multiset of objects. These are creation rules. In reaction with an object, a new membrane is created. This new membrane is placed inside of the membrane of the object which triggers the rule and has associated an initial multiset and a label. The rules are applied according to the following principles: •The rules are used as customary in the framework of membrane computing, that is, in a maximal parallel way. In one step, each object in a membrane 1Recently, new operations to change the membrane structure, such as merging membranes, or the operations of endocytosis,exocytosis or gemmation have been explored. 4 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez can only be used by one rule (non-deterministically chosen when there are several possibilities), but any object which can evolve by a rule of any form must do it (with the restrictions indicated below). •If a membrane is dissolved, its content (multiset and interior membranes) becomes part of the immediately external one. The skin membrane is never dissolved. •All the elements which are not involved in any of the operations to be applied remain unchanged. •The rules associated with the label lare used for all membranes with this label, irrespective of whether or not the membrane is an initial one or it was obtained by creation. •At one step, different rules can be applied to different membranes with the same label, but one membrane can just be the subject of only one rule of types (b), (c) or (d). •Several rules of the type (a) or (e) can be applied to different objects in the same membrane simultaneously. Hence, the rules of type (a) and (e) are applied in parallel, that is, all objects which can evolve by such rules must do it, while the rules of type (b), (c) and (d) are used sequentially, in the sense that one membrane can be used by at most one rule of these types in each step (time unit). The main difference with respect to the usual semantics of P systems with membrane creation is related to the communication rules (send-in and sendout). In [?,?,?], several objects can cross out one membrane simultaneously. On the contrary, in the semantics used in this paper, only one element can cross a membrane in each time unit. This is closer to the semantics of P systems with active membranes, where only one object can cross a membrane in one time unit. From a theoretical point of view, both semantics are acceptable and, as shown in this paper, NP-complete problems can be solved in both models. Another matter of discussion is the parallelism of the creation of new membranes. In this paper, in a similar way as in [?,?,?], several membranes can be created simultaneously inside one membrane, and there are no restrictions with respect to the label of the objects contained in the created membrane. Each of these semantics makes sense from a theoretical point of view. Another question is to know which of them is closer to the biological inspiration. Deciding the best semantics of these models is an open discussion in the P systems community. P Systems with Membrane Creation and Rule Input 5 3 Recognizer P systems with membrane creation Recognizer P systems were introduced in [?] and are the natural framework to study decision problems, since deciding if an instance has an affirmative or negative solution is equivalent to deciding if a word (yes or no) belongs or not to the language. In the literature, recognizer P systems are associated in a natural way with P systems with input. The data related to an instance of the decision problem has to be provided to the P system in order to compute the appropriate answer. The formal definition of such P systems consider a specific label and calls input membrane the membrane associated to this label. A multiset encoding the instance of the problem is then placed in the input membrane in the initial configuration and the computation starts. In this paper we propose a different way to supply the data related to the instance of the problem. In a similar way to the classical definition, a label is marked as input label, but instead of associating a multiset to the membrane with this label, we associate a set of rules which encodes the data of the problem. The main differences between this model and the classic model are: •The data of the instance is involved in the computation when the rules are triggered. •Since the membrane structure can change along the computation, the number of membranes with input label can also change. All these membranes are input membranes. This can be formalized as follows. Definition 1. AP system with rule input is a tuple (Π, iΠ, RiΠ), where Π is a P system, with working alphabet Γand nmembranes labelled by 1,...,n, and initial multisets w1,...,wnassociated with them, and a finite set of rules R,iΠis a distinguished label and RiΠis a set of rules disjoint of R. The set of rules RiΠis a new set of rules where the data of the problem is codified. It is associated to the input label iP i and it is added to the set of rules R. None of the rules from Ris modified. In a certain sense, providing the instance of the problem via a set of rules is the dual process of providing it as a multiset. In both cases, the information is provided before the computation starts and the P system acts as a black box, but, on the one hand, if we provide an initial multiset, these elements interact with a set of rules which do not depend on the instance of the problem. On the other hand, if the data is supplied as a set of rules, these rules have to interact with the object of an initial configuration which does not depend on the instance. 6 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez The way in which the user obtains the computed answer is similar to usual recognizer P systems. We use an external output in the classical way (see, for example, [?]). Definition 2. Arecognizer P system with rule input and with external output, is a P system with rule input (Π, iΠ, RiΠ), such that •The working alphabet contains two distinguished elements: yes,no. •All of its computations halt. •If Cis a computation of Π, then either an object yes or an object no (but not both) has to be sent out to the external environment, and only in the last step of the computation. Let us note that a recognizer P system with rule input is also a confluent system in the following sense: every computation with the same initial configuration has the same output. 4 Linear solution to the Subset Sum problem In this section we present a family Qof recognizer P systems with rule input that solves the Subset Sum problem in linear time. The Subset-Sum problem can be stated as follows: Given a finite set, A, a weight function, w:A→N, and a constant k∈N, determine whether or not there exists a subset B⊆Asuch that w(B) = k. If Ahas nelements with weights w1,...,wn, one instance of the problem can be encoded as (n, (w1,...,wn), k). As usual in the framework of P systems, the solution of the problem is based on an algorithm of brute force where an exponential amount of workspace is built in linear time. In a similar way to the solution of NP- problems with P systems with active membranes, the algorithm is split in four stages: •Generation stage: for every subset of A, a membrane is created. •Weight calculation stage: in each working membrane the weight of the associated subset is calculated. •Checking stage: in each membrane it is checked whether or not the weight of its associated subset is exactly k. •Output stage: when the previous stage has been completed in all membranes, the system sends out the answer (yes or no) to the environment. Next we describe the family Qof recognizer P systems with rule input that solves the Subset Sum problem. Given an instance (n, (w1,...,wn), k) of the P Systems with Membrane Creation and Rule Input 7 problem, the recognizer P system with rule input (Π, iΠ, RiΠ) is built, where Πis a P system which only depends on nand the input label iΠalso depends only on n. The data corresponding to this specific instance are provided in the set of rules RiΠwhich, obviously, depends on k, on the weights (w1,...,wn) and on the label iΠ. •Alphabet: O=        z0,...,z3n+11, a1,...an, na1,...,nan, w1,...,wn, s1,...,sn−1, u1,...,un−1, i, k, q, i0,...,i5, q0,...,q8, ba, ca, da, br, cr, dr, m1,...,m6, dr1, da1, c, c1, c2,#, no0, no1, h0,...,hn, yes0, . . . , yes3, fn1, fn2, fn3, yes, no        •Set of labels: H={e0, e1,...,en, r, a, dr, da, d, f, h} •Initial membrane structure: µ= [ ]e0. •Initial multiset Ms=z0a1na1 •The set Rof evolution rules consists of the following rules: (a) 2nrules [ai→[ai+1nai+1wi]ei]ei−1,for i= 1,...,n−1. [nai→[ai+1nai+1]ei]ei−1,for i= 1,...,n−1. [an→[wns1]en]en−1, [nan→[s1]en]en−1, These 2nrules create 2nmembranes at depth n(if the skin is at depth zero) in nsteps. Note how the objects w1,...,wnare distributed in the created membranes. If each object wiin a membrane ejwas sent to all children of ejand the process goes on until every wiwere in a elementary membrane, we would obtain each one of the 2nsubsets of {w1,...,wn}in one of the 2nelementary membranes. This is done by the next set of rules. (b)n2−nrules [wi→u2 i]ej, for i= 1,...,n−1 and j=i, . . . , n −1. ui[ ]ej→[wi]ej, for i= 1,...,n−1 and j=i+ 1,...,n. Each wihave to be sent to two membranes. This is done in two steps. In the first one, wievolves to two copies of uiand then, in the second step, each copy of uisend wiinto a child. (c)n−1 rules [si→si+1]en, for i= 1,...,n−2. [sn−1→ikq]en The membranes with label enare created with the element s1. This element is the first one of a sequence s1,...,sn−1which is used as a counter. When the element sn−1is reached, it evolves to the set {i, k, q}. The element k 8 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez will evolve in the next step to represent the value of the constant kin an unary representation. In the meanwhile, iand qevolve to i0and q0in a waiting step by using rules of the following set. (d)n−1 rules [ai→ai−1]en, for i= 2,...,n. [i→i0]en [q→q0]en Besides the waiting rules for iand k, we also have rules for decreasing the index of elements ai. By using this sequence {an,...,a1}we get the synchronous apparition of a multiset of elements a1which encodes the whole weight of the corresponding subset. (e) 16 rules [a1→ba, ca, da]en[r→br, cr, dr]en [ba →[m1]a]enca [ ]r→[c1]r[c1→c2]a [br →[m1]r]encr [ ]a→[c1]a[c1→c2]r [da →da1]en[da1→[m2]da]enca[ ]da →[c]da [dr →dr1]en[dr1→[m2]dr]encr[ ]dr →[c]dr [c2]a→# [c2]r→# The task of this set or rules is to compare the number of elements a1and rin each elementary membrane (labelled by en). The idea is the following: For each element a1a new element ca and a new membrane (labelled by a) will be created. Analogously, for each element ra new element cr and a new membrane (labelled by r) will be created. In the next steps, elements ca will be introduced (after renaming) into membranes labelled with r. These elements will produce the dissolution of such membranes. Analogously, elements cr will be introduced (after renaming) into membranes labelled with a. These elements will also produce the dissolution of such membranes. If the initial number of elements a1and rare the same, after an appropriate number of steps all the membranes labelled with aor rdisappear. Otherwise, a membrane labelled with aor rremains and it will be used as a flag for the computation in this membrane. This comparison has other technical details. For example, we do not desire that two objects ca go into the same membrane labelled with r, so we need extra rules, but the process is essentially as described above. (f)10 rules P Systems with Membrane Creation and Rule Input 9 [i→i0]en[i0→i1]en i5[ ]a→[i5]a[i1→i2]en i5[ ]r→[i5]r[i2→i3]en [i5]a→no0[i3→i4]en [i5]r→no0[i4→i5]en As we saw above, by using the rules from set (e), if the number of elements a1and rare the same, then all membranes labelled with aor rdissappear. But if this does not happen, after an appropriate number of steps, at least one of this type of membranes remains. In this set (f) we have 10 rules which are the complement to this process. We have a counter with an initial object i(generated via a rule of the set (c)) and the sequence i0, i1,...,i5. When i5appears, if there exists a membrane with label aor r, this element goes into the membrane and dissolves it sending the element no0. Otherwise, the element i5does not trigger any rule and the object no0does not appear. (g) 16 rules [m1→m2]a[m1→m2]r [m2→m3]a[m2→m3]r[m2→m3]da [m2→m3]dr [m3→m4]a[m3→m4]r[m3]da →# [m3]dr →# [m4→m5]a[m4→m5]r [m5→m6]a[m5→m6]r [m6]a→# [m6]r→# Membranes with label aor rare auxiliary membranes created for the comparison between the number of objects a1and r. When the comparison ends, these membranes are dissolved. This process is carried out by a counter. The membranes are created with the object m1. When the counter m1, m2,... reaches m6the membrane is dissolved. Membranes with labels da and dr are also created for the comparison. They catch the excess of objects ca and cr. When this work is done, they are also dissolved. (h)n+ 8 rules [qi→qi+1]en,for i= 0,...,7. [q8]ej→q8,for j= 2,...,n. [q8]e1→#, When the element q8is generated, it produces sequentially the dissolution of all membranes except the skin. (i) 9 rules 16 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez •Checking. In this stage 2nnew auxiliary membranes with label hare generated and the objects no0are sent into them. If there exists 2nobjects no0in the skin, all these membranes will stop their inner process and the object no is sent to the environment. If the number of no0in the skin is less than 2n, this means that at least one of the workspace membrane had a positive answer. In this case at least one of the membranes with label h is not stopped by no0and the object yes is sent to the environment. The simplification is performed by the object q8. It appears in all workspace membranes and dissolves them and the auxiliary membranes as well. In our example, at time 16 we have [z16, h8 3[q4 8#54i5no3 0]e1[q4 8#66i5no3 0]e1]e0 In the next step, both membranes at level 1 are dissolved under the action of object q8, but the counter hhas reached hnand 2nnew membranes with label hare created. At time 17, we have [z17,#122q6 8i5no3 0[yes0]8 h]e0 The computation follows as described above, and at time 20 we have [z20,#142yes2 3]e0 Here we find two objects yes0, but only one element yes has to be sent to the environment. This stage is managed by rules of the set (l). For that, new membranes with label dand fare created. Finally, at time 26 we have again only one membrane [#144fn3yes]e0 In the next step (time 27), the object yes is sent to the environment and the system reaches a halting configuration. 6 Some formal details We have presented a uniform family of P systems which solves the Subset Sum problem. The construction of the P systems is linear in the parameter n, in the number of objects of the alphabet, and quadratic in the number of rules, so each P system can be built in polynomial time. The number of steps of the P system is also linear in n: •3n+ 18 if the answer is yes, •3n+ 19 if the answer is no. P Systems with Membrane Creation and Rule Input 17 7 Conclusion and future work The key for solving NP-complete problems in the membrane computing framework is the possibility to generate an exponential workspace in polynomial time. The processes by which this exponential number of membranes is created in polynomial time are basically two: mitosis (membrane division) and autopoiesis (membrane creation). In this paper we explore a new semantics for P systems with membrane creation, closer to the semantics of P systems with active membranes than the semantics from [?,?,?]) and remark the necessity of set a standard semantics for this recently explored and fruitful model of P systems. The main novelty of this paper is the concept of P systems with rule input. As pointed above, in a certain sense, providing the instance of the problem via a set of rules is the dual process of providing it as a multiset, since the P system which solves a problem only depends on the size of the problem and we only provide the data in a different way. In one case, we modify the multisets placed in the initial configuration adding the data and the set of rules remains unchanged. In the second case, the initial configuration remains unchanged and the data is supplied by adding new rules which codify the information. One of the main drawbacks of this new approach is the fact that several membranes can be labelled with the input label (since new membranes with this label can be created) and in this way the input data can be supplied several times (even at different steps) along the computation and this feature goes against the simplicity principle. Therefore, a further and deeper study must be done in this line. Acknowledgement The support for this research through the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, is gratefully acknowledged. References 1. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A fast P system for finding a balanced 2-partition. Soft Computing, in press. 2. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: Solving SAT with membrane creation. Accepted paper for CiE 2005. 3. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: A linear solution for QSAT with membrane creation. Submitted. 18 M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez 4. M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, F.J. Romero-Campero: A linear solution of Subset Sum by using membrane creation. Submitted. 5. P.L. Luisi: The chemical implementation of autopoiesis. In Self-Production of Supramolecular Structures (G.R. Fleishaker et al., eds.), Kluwer, Dordrecht, 1994. 6. Gh. P˘aun: Further open problems in membrane computing. In Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘aun, A. Riscos, A. Romero, F. Sancho, eds.), Report RGNC 01/04, University of Seville, 2004, 354–365. 7. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Solving the Subset-Sum problem by active membranes. New Generation Computing, in press. 8. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A linear solution for the Knapsack problem using active membranes. In Membrane Computing (C. Mart´ın-Vide, G. Mauri, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), Lecture Notes in Computer Science,2933, 2004, 250–268. 9. M.J. P´erez-Jim´enez, F.J. Romero-Campero: Solving the BIN PACKING problem by recognizer P systems with active membranes. In Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘aun, A. Riscos, A. Romero, F. Sancho, eds.), Report RGNC 01/04, University of Seville, 2004, 414–430. 10. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini, F.: A polynomial complexity class in P systems using membrane division. In Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003 (E. Csuhaj-Varj´u, C. Kintala, D. Wotschke, Gy. Vaszyl, eds.), 2003, 284–294.