Spiking Neural P Systems with Neuron Division and Budding

Spiking Neural P Systems with Neuron Division and Budding Linqiang Pan1,2, Gheorghe P˘aun2,3, Mario J. P´erez-Jim´enez2 1Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected], [email protected] 2Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] 3Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania [email protected], [email protected] Summary. In order to enhance the efficiency of spiking neural P systems, we introduce the features of neuron division and neuron budding, which are processes inspired by neural stem cell division. As expected (as it is the case for P systems with active membranes), in this way we get the possibility to solve computationally hard problems in polynomial time. We illustrate this possibility with SAT problem. 1 Introduction Spiking neural P systems (in short, SN P systems) were introduced in [6] in the framework of membrane computing [13] as a new class of computing devices which are inspired by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. Since then, many computational properties of SN P systems have been studied; for example, it has been proved that they are Turing-complete when considered as number computing devices [6], when used as language generators [3, 1] and also when computing functions [12]. Investigations related to the possibility to solve computationally hard problems by using SN P systems were first proposed in [2]. The idea was to encode the instances of decision problems in a number of spikes which are placed in an arbitrarily large pre-computed system at the beginning of the computation. It was shown that the resulting SN P systems are able to solve the NP-complete problem SAT (the satisfiability of propositional formulas expressed in conjunctive normal form) in a constant time. Slightly different solutions to SAT and 3-SAT by using SN 152 L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez P systems with pre-computed resources were considered in [7]; here the encoding of an instance of the given problem is introduced into the pre-computed resources in a polynomial number of steps, while the truth values are assigned to the Boolean variables of the formula and the satisfiability of the clauses is checked. The answer associated with the instance of the problem is thus computed in a polynomial time. Finally, very simple semi-uniform and uniform solutions to the numerical NP-complete problem Subset Sum – by using SN P systems with exponential size pre-computed resources – have been presented in [8]. All the systems constructed above work in a deterministic way. A different idea of constructing SN P systems for solving NP-complete problems was given in [10, 11], where the Subset Sum and SAT problems were considered. In these papers, the solutions are obtained in a semi-uniform or uniform way by using non-deterministic devices but without pre-computed resources. However, several ingredients are also added to SN P systems such as extended rules, the possibility to have a choice between spiking rules and forgetting rules, etc. An alternative to the constructions of [10, 11] was given in [9], where only standard SN P systems without delaying rules and having a uniform construction are used. However, it should be noted that the systems described in [9] either have an exponential size, or their computations last an exponential number of steps. Indeed, it has been proved in [11] that a deterministic SN P system of a polynomial size cannot solve an NP-complete problem in a polynomial time unless P=NP. Hence, under the assumption that P6=NP, efficient solutions to NP-complete problems cannot be obtained without introducing features which enhance the efficiency of the system. In this paper, neuron division and budding are introduced into the framework of SN P systems in order to enhance the efficiency of these systems. We exemplify this possibility with a uniform solution to SAT problem. The biological motivation of introducing neuron division and budding into SN P systems comes from the recent discoveries in neurobiology related to neural stem cells – see, e.g., [4]. Neural stem cells persist throughout life within central nervous system in the adult mammalian brain, and this ensures a life-long contribution of new neurons to self-renewing nervous system with about 30000 new neurons being produced every day. Even in vitro, neural stem cells can be grown and extensively expanded for months. New neurons are produced by symmetric or asymmetric division. Two main neuron cell types are found: neuroblasts and astrocytes. The latter form a meshwork and are organized into channels. These observations are incorporated in SN P systems by considering neuron division and budding, and by providing a “synapse dictionary” according to which new synapses are generated, respectively. The paper is organized as follows. In Section 2 we recall some mathematical preliminaries that will be used in the following. In Section 3 the formal definition of SN P systems with neuron division rules and neuron budding rules is given. In Section 4 we present a uniform family of SN P systems with neuron division and budding rules such that the systems can solve SAT problem in a polynomial time. SN P Systems with Neuron Division and Budding 153 Section 5 concludes the paper and suggests some possible open problems for future work. 2 Prerequisites We assume the reader to be familiar with basic elements about membrane computing, e.g., from [13] and [14], and formal language theory, as available in many monographs. We mention here only a few notions and notations which are used through the paper. For an alphabet V,V∗denotes the set of all finite strings over V, with the empty string denoted by λ. The set of all nonempty strings over Vis denoted by V+. When V={a}is a singleton, then we simply write a∗and a+instead of {a}∗, {a}+. A regular expression over an alphabet Vis defined as follows: (i) λand each a∈Vis a regular expression, (ii) if E1, E2are regular expressions over V, then (E1)(E2), (E1)∪(E2), and (E1)+are regular expressions over V, and (iii) nothing else is a regular expression over V. With each regular expression Ewe associate a language L(E), defined in the following way: (i) L(λ) = {λ}and L(a) = {a}, for all a∈V, (ii) L((E1)∪(E2)) = L(E1)∪L(E2), L((E1)(E2)) = L(E1)L(E2), and L((E1)+) = (L(E1))+, for all regular expressions E1, E2over V. Non-necessary parentheses can be omitted when writing a regular expression, and also (E)+∪{λ} can be written as E∗. 3 SN P Systems with Neuron Division and Budding As stated in the Introduction, SN P systems have been introduced in [6], in the framework of membrane computing. They can be considered as an evolution of P systems, corresponding to a shift from cell-like to neural-like architectures. In SN P systems the cells (also called neurons) are placed in the nodes of a directed graph, called the synapse graph. The contents of each neuron consist of a number of copies of a single object type, called the spike. Every cell may also contain a number of firing and forgetting rules. Firing rules allow a neuron to send information to other neurons in the form of electrical impulses (also called spikes) which are accumulated at the target cell. The applicability of each rule is determined by checking the contents of the neuron against a regular set associated with the rule. In each time unit, if a neuron can use one of its rules, then one of such rules must be used. If two or more rules could be applied, then only one of them is non-deterministically chosen. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. Note that, as usually happens in membrane computing, a global clock is assumed, marking the time for the whole system, and hence the functioning of the system is synchronized. When a cell sends out spikes it becomes “closed” (inactive) for a specified period 154 L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez of time, a fact which reflects the refractory period of biological neurons. During this period, the neuron does not accept new inputs and cannot “fire” (that is, emit spikes). Another important feature of biological neurons is that the length of the axon may cause a time delay before a spike arrives at the target. In SN P systems this delay is modeled by associating a delay parameter to each rule which occurs in the system. If no firing rule can be applied in a neuron, then there may be the possibility to apply a forgetting rule, that removes from the neuron a predefined number of spikes. The structure of SN P systems (that is, the synapse graph) introduced in [6] is static. For both biological and mathematical motivations discussed in the Introduction, neuron division and budding are introduced into SN P systems. In this way, an exponential workspace can be generated in polynomial (even linear) time and computationally hard problems can be efficiently solved by means of a space-time tradeoff. Formally, a spiking neural P system with neuron division and budding of (initial) degree m≥1 is a construct of the form Π= (O, H, syn, n1, . . . , nm, R, in, out), where: 1. O={a}is the singleton alphabet (ais called spike); 2. His a finite set of labels for neurons; 3. syn ⊆H×His a synapse dictionary, with (i, i)6∈ syn for i∈H; 4. ni≥0 is the initial number of spikes contained in neuron i,i∈ {1,2, . . . , m}; 5. Ris a finite set of developmental rules, of the following forms: (1) extended firing (also called spiking) rule [E/ac→ap;d]i, where i∈H,E is a regular expression over a, and c≥1, p≥0, d≥0, with the restriction c≥p; (2) neuron division rule [E]i→[ ]jk[ ]k, where Eis a regular expression and i, j, k ∈H; (3) neuron budding rule [E]i→[ ]i/[ ]j, where Eis a regular expression and i, j ∈H; 6. in, out ∈Hindicate the input and the output neurons of Π. Note that we have presented here an SN P system in a way slightly different from the usual definition present in the literature, where the neurons present initially in the system are explicitly listed as σi= (ni, Ri), where 1 ≤i≤mand Ri are the rules associated with neuron with label i. In what follows we will refer to neuron with label i∈Halso denoting it with σi. It is worth to mention that by applying division rules different neurons can appear with the same label. In this context, (i, j)∈syn means the following: there exist synapses from each neuron with label ito each neuron with label j. If an extended firing rule [E/ac→ap;d]ihas E=ac, then we will write it in the simplified form [ac→ap;d]i; similarly, if a rule [E/ac→ap;d]ihas d= 0, then we can simply write it as [E/ac→ap]i; hence, if a rule [E/ac→ap;d]ihas SN P Systems with Neuron Division and Budding 155 E=acand d= 0, then we can write [ac→ap]i. A rule [E/ac→ap]iwith p= 0 is written in the form [E/ac→λ]iand is called extended forgetting rule. Rules of the types [E/ac→a;d]iand [ac→λ]iare said to be standard. If a neuron σicontains kspikes and ak∈L(E), k ≥c, then the rule [E/ac→ ap;d]iis enabled and it can be applied. This means consuming (removing) cspikes (thus only k−cspikes remain in neuron σi); the neuron is fired, and it produces pspikes after dtime units. If d= 0, then the spikes are emitted immediately; if d= 1, then the spikes are emitted in the next step, etc. If the rule is used in step tand d≥1, then in steps t, t + 1, t + 2, . . . , t +d−1 the neuron is closed (this corresponds to the refractory period from neurobiology), so that it cannot receive new spikes (if a neuron has a synapse to a closed neuron and tries to send a spike along it, then that particular spike is lost). In the step t+d, the neuron spikes and becomes open again, so that it can receive spikes (which can be used starting with the step t+d+ 1, when the neuron can again apply rules). Once emitted from neuron σi, the pspikes reach immediately all neurons σjsuch that there is a synapse going from σito σjand which are open, that is, the pspikes are replicated and each target neuron receives pspikes; as stated above, spikes sent to a closed neuron are “lost”, that is, they are removed from the system. In the case of the output neuron, pspikes are also sent to the environment. Of course, if neuron σi has no synapse leaving from it, then the produced spikes are lost. If the rule is a forgetting one of the form [E/ac→λ]i, then, when it is applied, c≥1 spikes are removed. When a neuron is closed, none of its rules can be used until it becomes open again. If (1) a neuron σicontains sspikes and as∈L(E), and (2) there is no neuron σg such that the synapse (g, i) or (i, g) exists in the system, for some g∈ {j, k}, then the division rule [E]i→[ ]jk[ ]kis enabled and it can be applied. This means that consuming all these sspikes the neuron σiis divided into two neurons, σjand σk. The new neurons contain no spike in the moment when they are created. They can have different labels, but they inherit the synapses that the father neuron already has (if there is a synapse from neuron σgto the neuron σi, then in the process of division one synapse from neuron σgto new neuron σjand another one from σgto σkare established; similarly, if there is a synapse from the neuron σito neuron σh, then one synapse from σjto σhand another one from σkto σhare established). Note that the restriction provided by condition (2) to the use of the rule ensures that no synapse (j, j) or (k, k) appears. Except for the inheritance of synapses, the new neurons produced by division can have new synapses as provided by the synapse dictionary. Note that during the computation, it is possible that a synapse between neurons involved in the division rule and neurons existing in the system will appear that is not in the synapse dictionary syn, because of the inheritance of synapses. Therefore, the synapse dictionary syn has two functions: one is to deduce the initial topological structure of the SN P system (a directed graph), for example, if there are neurons σ1, . . . , σkat the beginning of computation, then the initial topological structure of the system is syn ∩({1,2, . . . , k}×{1,2, . . . , k}); another function is to guide the synapse establishment associated with the new 156 L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez neurons generated by neuron division or neuron budding. That is why we call syn a synapses dictionary. If (1) a neuron σicontains sspikes, and as∈L(E), and (2) there is no neuron σjsuch that the synapse (i, j) exists in the system,then the budding rule [E]i→ [ ]i/[ ]jis enabled and it can be applied. This means that consuming all the s spikes a new neuron is created, σj. Both neurons are empty after applying the rule. The neuron σiinherits the synapses going to it before using the rule. The neuron σjcreated by budding by neuron σiinherits the synapses going out of σi before budding, that is, if there is a synapse from neuron σito some neuron σh, then a synapse from neuron σjto neuron σhis established (condition (2) ensures the fact that no synapse (j, j) appears). There is also a synapse (i, j) between neurons σiand σj. Except for the above synapses associated with neurons σiand σj, other synapses associated with neuron σjcan be established according to the synapses dictionary syn as in the case of neuron division rule. In each time unit, if a neuron σican use one of its rules, then a rule from Rmust be used. If several rules are enabled in neuron σi, irrespective of their types (spiking, dividing, or budding) then only one of them is chosen non-deterministically. When a spiking rule is used, the state of neuron σi(open or closed) depends on the delay d. When a neuron division rule or neuron budding rule is applied, at this step the associated neuron is closed, it cannot receive spikes. In the next step, the neurons obtained by division or budding will be open and can receive spikes. Thus, the rules are used in the sequential manner in each neuron, but neurons function in parallel with each other. It is worth noting here that the two neurons produced by a division rule can have labels different from each other and from the divided neuron, and that they are placed “in parallel”, while in the budding case the old neuron (consumes all its spikes and) produces one new neuron which is placed “serially”, after the neuron which budded. The configuration of the system is described by the topology structure of the system, the number of spikes associated with each neuron, and the state of each neuron (open or closed). Using the rules as described above, one can define transitions among configurations. Any sequence of transitions starting in the initial configuration is called a computation. A computation halts if it reaches a configuration where all neurons are open and no rule can be used. Traditionally, the input of an SN P system used in the accepting mode is provided in the form of a spike train, a sequence of steps when one spike or no spike enters the input neuron. In what follows we need several spikes at a time to come into the system via the input neuron, that is we consider “generalized spike trains”, written in the form ai1·ai2·...·air, where r≥1, ij≥0 for each 1 ≤j≤r. The meaning is that ijspikes are introduced in neuron σin in step j(all these ij spikes are provided at the same time). Note that we can have ij= 0, which means that no spike is introduced in the input neuron. The period which separate the “packages” aijof spikes is necessary in order to make clear that we do not have SN P Systems with Neuron Division and Budding 157 here a concatenation of the strings describing these “packages”, but a sequence of blocks (more formally, a sequence of multisets over the singleton alphabet O). Spiking neural P systems can be used to solve decision problems, both in a semi–uniform and in a uniform way. When solving a problem Qin the semi– uniform setting, for each specified instance Iof Qan SN P system ΠQ,Iis (i) built by a Turing machine in a polynomial time (with respect to the size of I), (ii) its structure and initial configuration depend upon I, and (iii) it halts (or emits a specified number of spikes in a given interval of time) if and only if Iis a positive instance of Q. On the other hand, a uniform solution of Qconsists of a family {ΠQ(n)}n∈Nof SN P systems that are built by a Turing machine in a polynomial time (with respect to the size n). When having an instance I ∈ Q of size n, we introduce a polynomial (in n) number of spikes in a designated input neuron of ΠQ(n) and the computation halts (or, alternatively, a specified number of spikes is emitted in a given interval of time) if and only if Iis a positive instance. The preference for uniform solutions over semi–uniform ones is given by the fact that they are more strictly related to the structure of the problem, rather than to specific instances. Indeed, in the semi–uniform setting we do not even need any input neuron, as the instance of the problem can be embedded into the initial configuration of the system from the very beginning. 4 A Uniform Solution to SAT Problem Let us consider the NP-complete decision problem SAT [5]. The instances of SAT depend upon two parameters: the number nof variables, and the number mof clauses. We recall that a clause is a disjunction of literals, occurrences of xior ¬xi, built on a given set X={x1, x2, . . . , xn}of Boolean variables. Without loss of generality, we can avoid the clauses in which the same literal is repeated or both the literals xiand ¬xi, for any 1 ≤i≤n, occur. In this way, a clause can be seen as a set of at most nliterals. An assignment of the variables x1, x2, . . . , xn is a mapping T:X→ {0,1}that associates to each variable a truth value. The number of all possible assignments to the variables of Xis 2n. We say that an assignment satisfies the clause Cif, assigned the truth values to all the variables which occur in C, the evaluation of C(considered as a Boolean formula) gives 1 (true) as a result. We can now formally state the SAT problem as follows. Problem 1. NAME: SAT. – INSTANCE: a set C={C1, C2, . . . , Cm}of clauses, built on a finite set {x1, x2, . . . , xn}of Boolean variables. – QUESTION: is there an assignment of the variables x1, x2, . . . , xnthat satisfies all the clauses in C? Equivalently, we can say that an instance of SAT is a propositional formula γn,m =C1∧C2∧· · ·∧Cm, expressed in the conjunctive normal form as a conjunction 158 L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez of mclauses, where each clause is a disjunction of literals built using the Boolean variables x1, x2, . . . , xn. With a little abuse of notation, from now on we will denote by SAT(n, m) the set of instances of SAT which have nvariables and mclauses. Let us consider the polynomial time computable function hn, mi= ((m+n)(m+ n+ 1)/2) + m(the pair function), which is a primitive recursive and bijective function from N2to N. Let us build a uniform family {ΠSAT (hn, mi)}n,m∈Nof SN P systems such that for all n, m ∈Nthe system ΠSAT (hn, mi) solves all the instances of SAT(n, m) in a number of steps which is linear in both nand m. All the systems ΠSAT (hn, mi) will work in a deterministic way. Because the construction is uniform, we need a way to encode any given instance γn,m of SAT(n, m). As stated above, each clause Ciof γn,m can be seen as a disjunction of at most nliterals, and thus for each j∈ {1,2, . . . , n}either xj occurs in Ci, or ¬xjoccurs, or none of them occurs. In order to distinguish these three situations we define the spike variables αi,j, for 1 ≤i≤mand 1 ≤j≤n, as variables whose values are amounts of spikes; we assign to them the following values: αi,j =   a, if xjoccurs in Ci; a2,if ¬xjoccurs in Ci; a0,otherwise. In this way, clause Ciwill be represented by the sequence αi,1·αi,2·. . . ·αi,n of spike variables; in order to represent the entire formula γn,m we just concatenate the representations of the single clauses, thus obtaining the generalized spike train α1,1·α1,2·. . . ·α1,n.α2,1·α2,2·. . . ·α2,n ·...·αm,1·αm,1·...·αm,n. As an example, the representation of γ3,2= (x1∨¬x2)(x1∨x3) is the sequence a·a2·a0·a·a0·a. In order to let the systems have enough time to generate necessary workspace before computing the instances of SAT(n, m), a spiking train (a0·)2nis added in front of the formula encoding spike train α1,1·α1,2·. . . ·α1,n.α2,1·α2,2·. . . ·α2,n ·. . . · αm,1·αm,1·...·αm,n. In general, for any given instance γn,m of SAT (n, m), the encoding sequence is cod(γn,m) = (a0·)2nα1,1·α1,2·...·α1,n ·α2,1·α2,2·. . . ·α2,n · . . . ·αm,1·αm,1·. . . ·αm,n. For each n, m ∈N, we construct Π(hn, mi) = (O, H, syn, n1, . . . , nq, R, in, out), with the following components: The initial degree of the system is q= 4n+ 7; O={a}; H={in, out, cl}∪{di|i= 0,1, . . . , n} ∪ {Cxi|i= 1,2, . . . , n}∪{Cxi0|i= 1,2, . . . , n} ∪ {Cxi1|i= 1,2, . . . , n}∪{ti|i= 1,2, . . . , n} ∪ {fi|i= 1,2, . . . , n}∪{0,1,2,3}; SN P Systems with Neuron Division and Budding 159 syn ={(di, di+1)|i= 0,1, . . . , n −1}∪{(dn, d1)} ∪ {(in, Cxi)|i= 1,2, . . . , n}∪{(di, Cxi)|i= 1,2, . . . , n} ∪ {(Cxi, Cxi0) |i= 1,2, . . . , n}∪{(Cxi, Cxi1) |i= 1,2, . . . , n} ∪ {(i+ 1, i)|i= 0,1,2}∪{(1,2),(0, out)} ∪ {(Cxi1, ti)|i= 1,2, . . . , n}∪{(Cxi0, fi)|i= 1,2, . . . , n}; nd0=n0=n2=n3= 1, nd1= 6, and there is no spike in the other neurons; Ris the following set of rules: (1) spiking rules: [a→a]in, [a2→a2]in, [a→a; 2n+nm]d0, [a4→a4]i,i=d1, . . . , dn, [a5→λ]d1, [a6→a4; 2n+ 1]d1, [a→λ]Cxi,i= 1,2, . . . , n, [a2→λ]Cxi,i= 1,2, . . . , n, [a4→λ]Cxi,i= 1,2, . . . , n, [a5→a5;n−i]Cxi,i= 1,2, . . . , n, [a6→a6;n−i]Cxi,i= 1,2, . . . , n, [a5→a4]Cxi1,i= 1,2, . . . , n, [a6→λ]Cxi1,i= 1,2, . . . , n, [a5→λ]Cxi0,i= 1,2, . . . , n, [a6→a4]Cxi0,i= 1,2, . . . , n, [(a4)+→a]ti,i= 1,2, . . . , n, [(a4)+→a]fi,i= 1,2, . . . , n, [a4k−1→λ]ti,k= 1,2, . . . , n,i= 1,2, . . . , n, [a4k−1→λ]fi,k= 1,2, . . . , n,i= 1,2, . . . , n, [am→a2]cl, [(a2)+/a →a]out, [a→a]i,i= 1,2, [a2→λ]2, [a→a; 2n−1]3; (2) neuron division rules: [a]0→[ ]t1k[ ]f1, [a]ti→[ ]ti+1 k[ ]fi+1 ,i= 1,2, . . . , n −1, [a]fi→[ ]ti+1 k[ ]fi+1 ,i= 1,2, . . . , n −1; (3) neuron budding rules: [a]tn→[ ]tn/[ ]cl, [a]fn→[ ]fn/[ ]cl. 166 L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez 4. Number of labels for neurons: 6n+ 8 ∈O(n). 5. Size of synapse dictionary: 7n+ 6 ∈O(n). 6. Number of rules: 2n2+ 14n+ 12 ∈O(n2). 5 Conclusions and Remarks With computer science and biological motivation, neuron division and neuron budding are introduced into the framework of spiking neural P systems. We have proven that spiking neural P systems with neuron division and neuron budding can solve NP-complete problems in polynomial time. We exemplify this possibility with SAT problem. Both neuron division rules and neuron budding rules can generate exponential workspace in linear time. In this sense, we used a double “power” to solve SAT problem in the systems constructed in this paper. It remains open to design efficient spiking neural P systems with either neuron division rules or neuron budding rules, but not both kinds of rules, for solving NP-complete problem. Actually, we have here a larger set of problems. Besides the budding rules of the form considered above, we can also define “serial division rules”, of the form [E]i→[ ]j/[ ]k, where Eis a regular expression and i, j, k ∈H. The meaning is obvious: neuron σiproduces two neurons, σjand σk, with possibly new labels j, k, linked by synapses as in the case of budding rules. Note that a budding rule is a particular case, with i=j. Thus, we can consider three types of rules: parallel division rules, budding rules (these two types were considered above), and serial division rules. Are rules of a single type sufficient in order to devise SN P systems which solve computationally hard problems in polynomial time? For cell-like P systems, besides membrane division, there is another operation which was proved to provide ways to generate an exponential workspace in polynomial time, useful for trading space for time in solving NP-complete problem, namely membrane creation (a membrane is created from objects present in other membranes). Can this idea be also extended to SN P systems? Note that in the case of SN P systems we do not have neurons inside neurons, neither spikes outside neurons, hence this issue does not look easy to handle; maybe further ingredients should be added, such as glia cells, astrocytes, etc. Acknowledgements Valuable comments from Jun Wang are greatly appreciated. The work of L. Pan was supported by National Natural Science Foundation of China (Grant Nos. 60674106, 30870826, 60703047, and 60803113), Program for New Century Excellent Talents in University (NCET-05-0612), Ph.D. Programs Foundation of Ministry of Education of China (20060487014), Chenguang Program of Wuhan (200750731262), HUST-SRF (2007Z015A), and Natural Science Foundation of SN P Systems with Neuron Division and Budding 167 Hubei Province (2008CDB113 and 2008CDB180). The work of the last two authors was supported by Project of Excellence with Investigador de Reconocida Valia, from Junta de Andalucia, grant P08 – TIC 04200. References 1. H. Chen, R. Freund, M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez: On string languages generated by spiking neural P systems. Fundamenta Informaticae, 75 (2007), 141– 162. 2. H. Chen, M. Ionescu, T.-O. Ishdorj: On the efficiency of spiking neural P systems. Proceedings of the 8th International Conference on Electronics, Information, and Communication, Ulanbator, Mongolia, June 2006, 49–52. 3. H. Chen, M. Ionescu, T.-O. Ishdorj, A. P˘aun, Gh. P˘aun, M.J. P´erez-Jim´enez: Spiking neural P systems with extended rules: universality and languages. Natural Computing, 7, 2 (2008), 147–166. 4. R. Galli, A. Gritti, L. Bonfanti, A.L. Vescovi: Neural stem cells: an overview. Circulation Research, 92 (2003), 598–608. 5. M.R. Garey, D.S. Johnson: Computers and Intractability. A Guide to the Theory of NP-completeness. W.H. Freeman and Company, San Francisco, 1979. 6. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2–3 (2006), 279–308. 7. T.-O. Ishdorj, A. Leporati: Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. Natural Computing, 7, 4 (2008), 519–534. 8. A. Leporati, M.A. Guti´errez-Naranjo: Solving Subset Sum by spiking neural P systems with pre-computed resources. Fundamenta Informaticae, 87, 1 (2008), 61–77. 9. A. Leporati, G. Mauri, C. Zandron, Gh. P˘aun, M.J. P´erez-Jim´enez: Uniform solutions to SAT and Subset Sum by spiking neural P systems. Natural Computing, online version (DOI: 10.1007/s11047-008-9091-y). 10. A. Leporati, C. Zandron, C. Ferretti, G. Mauri: Solving numerical NP-complete problem with spiking neural P systems. Lecture Notes in Computer Sci., 4860 (2007), 336–352. 11. A. Leporati, C. Zandron, C. Ferretti, G. Mauri: On the computational power of spiking neural P systems. International Journal of Unconventional Computing, 2007, in press. 12. A. P˘aun, Gh. P˘aun: Small universal spiking neural P systems. BioSystems, 90, 1 (2007), 48–60. 13. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. 14. The P systems Website: http://ppage.psystems.eu.