Spiking Neural P Systems: Stronger Normal Forms

Spiking Neural P Systems: Stronger Normal Forms Marc Garc´ıa-Arnau1, David Per´ez1, Alfonso Rodr´ıguez-Pat´on1, Petr Sos´ık1,2 1Universidad Polit´ecnica de Madrid - UPM, Facultad de Inform´atica Campus de Montegancedo s/n, Boadilla del Monte 28660 Madrid, Spain [email protected] 2Institute of Computer Science, Silesian University 74601 Opava, Czech Republic [email protected] Summary. Spiking neural P systems are computing devices recently introduced as a bridge between spiking neural nets and membrane computing. Thanks to the rapid research in this field there exists already a series of both theoretical and application studies. In this paper we focus on normal forms of these systems while preserving their computational power. We study combinations of existing normal forms, showing that certain groups of them can be combined without loss of computational power, thus answering partially open problems stated in [8, 9]. We also extend some of the already known normal forms for spiking neural P systems considering determinism and strong acceptance condition. Normal forms can speed-up development and simplify future proofs in this area. 1 Introduction Spiking neural P systems (SN P systems) are a rather new bio-inspired computational model that incorporates to membrane computing [6] some ideas from spiking neurons [3], [4]. Since they were first presented in [2], the number of publications dealing with this model is constantly growing. An interesting review on the current research topics in SN P systems can be found in [9]. Informally, an SN P system consists of a set of neurons placed in the nodes of a graph that are linked by synapses. These neurons send signals (spikes) along the arcs of the graph. To do so, the neurons contain firing or spiking rules which are of the form E/ar→a;twith Ebeing a regular expression, rbeing the number of spikes consumed by the rule and tbeing the delay from firing the rule and emitting the spike. A firing rule can be only used if the number nof spikes collected by the neuron is such that an∈L(E),that is, anis covered by the regular expression E, and n≥r. The neurons also have an interesting feature imitating the refractory period of real neural cells. Thus, a neuron in an SN P system is closed/blocked 158 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik for exactly ttime steps after firing. During this period it cannot fire again. The second type of rules have the form as→λand are called forgetting rules. They are used to simply forget (remove) sspikes from a cell. SN P systems start from an initial configuration of spikes and evolve in a synchronized manner (a global clock is assumed for the whole system). One of the neurons is designated as the output cell and the spikes it sends to the environment constitute the output of the system. The first work in SN P systems [2] presented them as devices generating or accepting sets of natural numbers. Their universality was proven when no bound is imposed on the number of spikes. Otherwise, only a characterization of semilinear sets is obtained. Later, a new paper [8] dealing with normal forms of the model attacked its universality trying to improve the previous proofs. In that article, universality results were obtained even if some of the main features of the model were weakened. For instance, universality was proven even without the use of delays. Furthermore, the outdegree of neurons was reduced to the minimal bound of two. Next, SN P systems were found to be also universal when forgetting rules were removed and, finally, computational completeness was still achieved when using the simplest possible regular expressions λand a∗over the alphabet {a}in firing rules. Another work [10] has also shown that not only the outdegree but also the indegree of neurons can be bound to two without loosing universality. In the present paper, we deal with some of the open problems stated in [8]. Actually, we try to keep the universality of the model when eliminating two of its key features simultaneously. Interesting results have been obtained. Surprisingly, SN P systems are still universal when we use neither delays nor forgetting rules. Moreover, one can also eliminate delays while simplifying regular expressions and the model keeps its computational completeness. Finally, we have proven the universality of the model in two more cases: 1) using simple regular expressions with strong halting condition and 2) using simple regular expressions with SN P systems working in the accepting mode. In all these cases, the reader will observe that the simultaneous elimination of two features of the model has a price in terms of other complexity parameters, such as the maximal number of firing rules in a neuron, the complexity of regular expressions, the maximum number of spikes consumed in a firing rule or the maximal number of spikes removed in a forgetting rule. The remainder of the paper is organized as follows. Section 2 presents some important definitions. In section 3 we present the universality result of the model using neither delays nor forgetting rules. Section 4 describes the power of SN P systems with simple regular expressions that do not use delays. Some more aspects concerning regular expressions are revisited in section 5. The paper concludes with some final remarks in section 6. Spiking Neural P Systems: Stronger Normal Forms 159 2 Definitions In this section, we recall some useful definitions. We consider the reader to be familiar with elements of membrane computing. One can find in [11] the most updated information on this area. The reader is considered to be familiar with elements of language and automata theory, as well. Nevertheless, we recall some basic notation. Let Vdenote an alphabet, while V∗denotes the set of all finite strings of symbols from V. The set of nonempty strings over Vis denoted by V+and λdenotes the empty string. The length of a string x∈V∗is denoted by |x|. In the domain of SN P systems, the alphabet V contains only one symbol, i.e., the alphabet is a singleton V={a}.Then a∗and a+are normally used instead of {a}∗and {a}+. Aspiking neural membrane system (abbreviated as SN P system), of a degree m≥1, is a construct of the form Π= (O, σ1,...,σm, syn, i0), where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1,...,σmare neurons, of the form σi= (ni, Ri),1≤i≤m, where: a) ni≥0 is the initial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) E/ar→a;t, where Eis a regular expression over a,r≥1, and t≥0; (2) as→λ, for some s≥1, with the restriction that for each rule E/ac→ a;dof type (1) from Ri, we have as/∈L(E); 3. syn ⊆ {1,2,...,m} × {1,2,...,m}with (i, i)/∈syn for 1 ≤i≤m(synapses between neurons); 4. i0∈ {1,2,...,m}indicates the output neuron (i.e., σi0is the output neuron). The rules of type (1) are firing rules (also called spiking rules). The notation E/ar→a, t means that when the number of spikes present in a neuron is covered by the regular expression E, the neuron gets fired, rspikes are consumed and, after ttime steps, one spike is emitted by the neuron to all its neighbors (the system is synchronized, a global clock is assumed for all its cells). In a SN P system we have maximal parallelism at the level of the system as, in one step, all neurons that can use a rule have to use it. However, at the neuronal level, we work in a sequential mode with at most one rule used in each step by a neuron. SN P systems also incorporate an interesting bio-inspired feature called the refractory period. In the interval between using a spiking rule (getting fired) and releasing the spike, the neuron is assumed to be closed (it omits any other spike received during this interval and, of course, it cannot fire). Then, if t= 0 160 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik there is no restriction and the neuron can receive spikes in the same step it uses the rule. Similarly, a neuron can receive spikes in moment twhen t≥1. When a neuron spikes, its spike is replicated to all its neighboring neurons that are not closed in that moment. These spikes are available in the receiving neuron already in the next step, so the transmission of a spike takes no time. The rules of type (2) are called forgetting rules. They are written as as→λ and they can be applied only when the neuron contains exactly sspikes. After applying one of these rules, sspikes are simply removed from the cell. Firing rules can be used in a non-deterministic way, that is, a neuron may contain two firing rules E1/ar1→a;t1and E2/ar2→a;t2such that L(E1)∩L(E2)6= ∅. However, this non-determinism is not allowed between firing and forgetting rules, that is, in a single step a neuron has either to fire or forget, without being possible to freely choose between these two actions. This is called the minimal determinismlike restriction or the coherence condition. Hence, we just allow branching in the case of spiking rules. We define a computation of an SN P system as a sequence of steps during which rules are applied in the above described parallel manner. A computation starts in the initial configuration when each neuron σicontains nispikes, 1 ≤i≤m. A halting computation is that in which the system reaches a configuration where no more rules can be applied. A computation is called strong halting if, in addition, no spike is present in the system when it halts. The usual way of interpreting outputs of SN P systems is considering intervals in which the output neuron i0spikes (not when it fires). For simplicity, one considers as successful only computations with the output neuron spiking at least twice. The set of numbers computed by an SN P system in this way is denoted by N2(Π). If we take into consideration only the computations having exactly 2 spikes (strong case) then this set is written as N2(Π). Similarly, if only halting (strong halting) computations are taken into the account, we denote the resulting sets by Nh 2(Π) (Nh 2(Π), respectively). The reader will find in [7] and [8] several other relevant definitions. We denote by Spikβ 2Pm(rulek, consp, forgq, dleyr, outds) the family of all sets Nβ 2(Π) (with β={h, h}), for all systems Πwith at most mneurons, each neuron having at most krules, each of the spiking rules consuming at most pspikes, each of the forgetting rules removing no more than qspikes, with all spiking rules having a delay small or equal to rand with all neurons having at most soutgoing synapses. We also may write rule∗ kif the firing rules are of the form E/ar→a;t with the regular expression of one of the forms E=λor E=a∗(in the former case the rule is written as ar→a;tto simplify). Finally, we define a register machine, which is the computational model used to prove the universality of SN P systems, as it is known (see [5]) that register machines (even with a small number of registers, although this detail is not relevant here) characterize NRE. Aregister machine is a construct M= (m, H, l0, lh, I), where mis the number of registers, His the set of instruction labels, l0is the start label (labeling an Spiking Neural P Systems: Stronger Normal Forms 161 ADD instruction), lhis the halt label (assigned to the instruction HALT), and Iis the set of instructions. Each label from Hlabels only one instruction from I(but the same instruction may be assigned to more labels). The instructions are of the following forms: •l1: (ADD(r), l2, l3) (add 1 to register rand then go to one of the instructions with labels l2, l3), •l1: (SUB(r), l2, l3) (if register ris non-empty, then subtract 1 from it and go to the instruction with label l2, otherwise go to the instruction with label l3), •lh:HALT (the halt instruction). A register machine Mcomputes a number nin the following way: we start with all registers empty (storing the number zero), we apply the instruction with label l0and we proceed to apply instructions as indicated by the labels (and made possible by the contents of registers). If we reach the halt instruction, then the number nstored at that time in the first register is said to be computed by M. Therefore N(M) denotes the set of all numbers computed by the register machine M. Without loss of generality, we may assume in the next sections that in the halting configuration, all registers different from the first one are empty, and that the output register is never decremented during the computation, we only add to its contents. A register machine can also work in the accepting mode: a number nis introduced in the first register (all other registers are empty) and we start computing with the instruction with label l0; if the computation eventually halts, then the number nis accepted. Register machines are universal also in the accepting mode; moreover, this is true even for deterministic machines, having ADD rules of the form l1: (ADD(r), l2, l3) with l2=l3(in such a case, the instruction is written in the form l1: (ADD(r), l2)). Again, without loss of generality, we may assume that in the halting configuration all registers are empty. 3 Removing Delays and Forgetting Rules Simultaneously In this section we extend the original result of Theorem 3.1 of [2], paying special attention to delays and forgetting rules. As it was shown in [8], computational completeness is achieved when eliminating each one of these two parameters separately. Here, we extend these results demonstrating that SN P Systems are also universal when eliminating both delays and forgetting rules at the same time. Simultaneously, we have also bounded the outdegree of neurons to two. However, for the sake of clarity, we don’t show it graphically in our demonstration. Nevertheless, this elimination has a price in terms of other parameters. Namely, the maximal number of rules used in a neuron rises to three and we lose the strong halting condition. As all rules we use have delay 0, we write them in the simpler form E/ar→a, that is, omitting the delay. 162 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik Theorem 1. Spikβ 2P∗(rule3, cons3, forg0, dley0, outd2) = NRE,where β=hor βis omitted. Proof. The inclusion Spikβ 2P∗(rule∗, cons∗, forg∗, dley∗, outd∗)⊆NRE is straightforward and therefore we omit it (Turing-Church thesis). To complete the proof we must show NRE ⊆Spikβ 2P∗(rule3, cons3, forg0, dley0, outd2). As in other demonstrations, we will construct an SN P system (Π) spiking only twice, at an interval of time which corresponds to a number computed by a register machine M. Our system consists of modules simulating the ADD and SUB instructions and the output module FIN which takes care of the final spiking of the system Π. Every register rof Mwill be associated to a neuron of Π. However, in contrast with some other previous demonstrations, a register containing the value nwill hold 2n+ 2 spikes. Any register representing the value 0 will therefore contain a couple of spikes. This slight modification in the way of representing numbers will allow us to detect correctly whether a register contains the value 0 in the SUB module without making use of delays or forgetting rules. Simulating an ADD instruction li: (ADD(r), lj, lk) – module ADD (Figure 1). This instruction adds one to the register rand branches non-deterministically to label ljor lk. This module is initiated when a spike enters neuron li(we can assume that the initial instruction of M, labeled with l0, is always an ADD instruction). The neuron lisends then one spike to neurons c1and c2. In the next step, one spike coming from each of these neurons reaches the neuron r, adding one to the content of the register. At the same time, the spike emitted by c1arrives to c3(which will in turn be send to c6in the following step) and c4, while the spike of c2reaches c4and c5. Neuron c4will allow us to branch non-deterministically to either ljor lk. If c4uses the rule a2→a, then two spikes will be blocked in c8(those coming from c4and c5), while just one will arrive to neuron c7waiting for another one to come. In the next step, the spike from c6reaches also c7and it gets fired, activating neuron ljone step later. On the other hand, if c4uses the rule a2/a →ait consumes only one of its two spikes. This means that, in the following step, c7receives one spike and c8receives two (from c4and c5). One step later, c4uses its rule a→aand sends another spike to c7(which also receives the one from c6and therefore cannot fire) and to c8that now contains three spikes and fires, activating lkin the following step. The reader will appreciate that, after each ADD instruction, neurons c7and c8will hold 3 or 2 spikes, respectively, depending on the rule selected in the nondeterministic neuron c4. Thanks to the regular expressions used in the rules of c7 and c8, this does not disturb further computations using this instruction. In this construction, neurons c1and c2have an outdegree of three. However, it is trivial to see that it could be reduced to two by placing more neurons between them and neurons c3, c4and c5, as it is explained in Section 5 of [8]. Simulating a SUB instruction li: (SUB(r), lj, lk) – module SUB (Figure 2). Spiking Neural P Systems: Stronger Normal Forms 163 Fig. 1. Module ADD (simulating li: (ADD(r), lj, lk)) The module is initiated when a spike is sent to neuron li. This neuron fires and its spike reaches neurons d1, d2and r. The three rules of neuron rallow us to differentiate whether the register is empty or not. As we have previously explained, storing the value nmeans to contain 2n+ 2 spikes. Thus, when r > 0, (i.e., it contains at least 4 spikes) the spike coming from limakes the neuron fire (rule aaa(aa)+/a3→a) sending a spike to d4and d5. At the same time, another spike coming from d2reaches d5, not allowing it to fire. In parallel, a spike is sent from d1to d3and, in the following step, it arrives to d4. This neuron fires because it already contains two spikes, allowing us to finally reach lj. On the other hand, when rstores number zero (it contains 2 spikes), the spike received from lifires the rule a3/a2→a. Then neuron rspikes, consuming two of the three spikes it contains. This spike is sent to neurons d4and d5. Another spike reaches d5simultaneously (from d2), while d3receives the spike coming from d1. In the following step, rfires again (using the rule a→a), consuming its last spike and sending a new spike to d4and d5(the value 0 of ris now degraded and needs to be reconstituted). This spike reaches neuron d4at the same time that the one coming from d3. Then d4cannot fire as it contains now three spikes. Meanwhile, d5receives the new spike from r(d5now contains three spikes). It gets fired and spikes, allowing neurons d6and d8to fire in the following step. Each of these two 164 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik Fig. 2. Module SUB (simulating li: (SUB(r), lj, lk)) neurons emits then one spike to rwhich reconstitute the value 0 in the register before reaching lk. The reader can check that the remaining spikes in neurons d4and d5do not disturb further computations. In this case, the outdegree can also be easily reduced to two using a couple of intermediate neurons between liand d1, r and d2. Ending a computation – module FIN (Figure 3). When the computation in Mhalts, a spike reaches the neuron lhof Π. In that moment, register 1 of Mstores value nand neuron 1 of Πcontains 2n+ 2 spikes. The spike emitted by lhreaches neuron 1 (thus containing an odd number of spikes). This leads neuron 1 to fire continuously, consuming two spikes at each step. One step after receiving the spike from lh, neuron 1 fires and one spike reaches neuron e1and neuron out. Next, neuron out fires and spikes for the first time. From that step on, neuron out simultaneously receives a couple of spikes from 1 and e1 that do not let it fire again until one step after neuron 1 fires for the last time. When neuron 1 stops spiking, neuron out still receives one spike from e1making it fire and emitting its second and last spike (exactly nsteps after the first one). Spiking Neural P Systems: Stronger Normal Forms 165 Fig. 3. The FIN module Once the computation has ended, neuron 1 holds three spikes and neuron out contains 2(n−1) spikes. As this construction needs to leave some spikes in the system after halting, it cannot be extended to the case of the strong halting. ut 4 Removing Delays and Simplifying Regular Expressions Theorem 7.1 of [8] stated that the regular expressions used in firing rules could be simplified to the point of just using the simplest expressions over the alphabet {a}:λand a∗. In this section we consider the same problem, but removing delays simultaneously. Surprisingly, the proof construction shows that SN P systems are still universal even in that case. Moreover, we keep universality using, in each neuron, one rule of the form a∗/a →aor (ar→a), and at most two rules as→λ, with r, s ≤3. (with the only exception of the non-deterministic neuron c3in the ADD module). Finally, we have also kept the limitation of outdegree ≤2 for each neuron. Comparing this result with that of Theorem 7.1 of [8], one can notice that removing delays has some computational cost in terms of other parameters, as the maximum degree of forgetting rules, the number of rules per neuron and the maximum number of spikes consumed in a rule. Theorem 2. Spikβ 2P∗(rule∗ 3, cons3, forg3, dley0, outd2) = NRE,where either β= hor βis omitted. Proof. This proof is based on that of Theorem 7.1 from [8], trying of imitate, as long as possible, the structure and functioning of modules ADD, SUB and FIN as 172 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik Ending a Computation – module FIN (Figure 9). The module FIN has also the same behavior as that of Theorem 7.1 in [8]. However, as in the case of module SUB, some structural changes have been made to eliminate the delays of neurons lh, c9, c10, d9and d10. On the one hand, both neurons c9and d9are substituted by two basic cells with delay zero. On the other hand, as neurons c10 and d10 make use of their refractory period, we replace each of them by one of our subsystems of type Πd1. Finally, neurons c2, c7, d7, c8and d8are duplicated to keep outdegree ≤2. Again, for the sake of clarity, we do not replace c3with its corresponding four basic neurons. ut 5 Simplified Regular Expressions Revisited Unlike some other results in [8], Theorem 7.1 mentioned above considered neither the case of strong halting, nor the case of accepting SN P systems. This sections extends this result and shows that it remains valid even if these additional restrictions are imposed. First we deal with the strong halting case. Theorem 3. Spikh 2P∗(rule∗ 2, cons2, forg2, dley2, outd2) = NRE. Proof. Considering the strong halting case, the construction in the proof of Theorem 7.1 in [8] has to be changed slightly. Recall the assumption that all the registers except register 1 are empty at the end of computation. Under this assumption, one can verify by inspection of the above mentioned proof that the only neurons containing spikes at the moment of halting are in the module FIN. To remove these spikes, we have to release the additional restriction we stated in [8]: the rules of the form ar→a;tand as→λin the same neuron satisfy s < t. Removing this restriction allows to simplify dramatically the construction, while keeping all other properties of the normal form. The new module FIN which satisfies the strong halting condition can be found in Figure 10. Function of the module FIN is described in Table 1. Assume that the output register 1 holds a value n≥1.Accordingly, the cycle consisting of neurons 1 and c1contains nspikes (n−1 in neuron 1 and one spike in neuron c1). Both neurons fire at every step (except the case n= 1 which will be dealt with later.) At step 1 neuron lhreceives spike and fires. At step 2 both neurons c2and c3receive spikes and start to fire at every step. Neuron c4receives at every step two spikes which are removed. From now on the number of spikes the cycle 1 −c1 decreases by one at every step. The output neuron out fires first time at step five. After n+ 2 steps all the spikes in the cycle 1 −c1are removed. At step n+ 3 neuron c2receives no spike and does not fire. Consequently, at step n+ 4 neuron c4receives only one spike and fires. Finally, at step n+ 5,exactly nsteps after its first firing, neuron out fires second time. The case n= 1 needs a special attention. In this case neuron 1 fires at every even step and c1fires at every odd step. For a correct function of the module FIN, neuron lhmust receive spike at an odd step. However, this is already taken care Spiking Neural P Systems: Stronger Normal Forms 173 Fig. 9. Module FIN (ending the computation) 174 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik Fig. 10. Module FIN with simplified regular expressions and strong halting state of in the proof of Theorem 7.1 in [8], as each instruction of the register machine is simulated in exactly 6 steps of the SN P system. Hence neuron lhwould receive spike at a step 6k+ 1, k ≥0,and the module FIN would function correctly again. Finally, note that the module FIN of Figure 10 contains neurons with outdegree three. This version of the module was presented for the sake of simplicity, but it can be easily enhanced so that outdegree is reduced to two. The resulting diagram is shown in Figure 11. ut Another extension of the previous result in [8] mentioned above is the case of accepting SN P systems. In the accepting mode [2], the SN P system obtains an input in the form of an interval between two consecutive spikes sent from outside to the input neuron i0.Therefore, we need a special module INPUT which translates this input value into the number of spikes present in a neuron labeled 1. Furthermore, the SN P system must behave deterministically. Both conditions can be satisfied and the resulting statement is given bellow. Theorem 4. DSpikβ 2accP∗(rule∗ 2, cons2, forgα, dley2, outd2) = NRE where (i) β=h, α = 1,or (ii) β=h, α = 2,or (iii) βis omitted and α= 1. Proof. Considering the proof Theorem 7.1 in [8], we can observe that the module SUB is already deterministic. Then it remains only to “determinize” the module ADD and add a module INPUT. For the former goal, it is enough to remove the Spiking Neural P Systems: Stronger Normal Forms 175 Step 1 2 3 4 5 . . . Neuron lha→a! — — — — . . . 1a→a!a→a!a→a!a→a!a→a! . . . (spikes) n−1n−1n−1n−2n−3 . . . c1a→a!a→a!a2→λ a2→λ a2→λ. . . c2—a2→a!a2→a!a2→a!a2→a! . . . c3—a→a!a→a!a→a!a→a! . . . c4— — a2→λ a2→λ a2→λ. . . c5—a→a; 2 — ! — . . . out — — — — a→a! . . . Step . . . n+ 1 n+ 2 n+ 3 n+ 4 n+ 5 Neuron lh. . . — — — — — 1 . . . a→a! — — a→a! — (spikes) . . . 1 0 0 1 0 c1... a2→λ a2→λ a →a! — a2→λ c2... a2→a!a2→a!a→λ a →λ a →λ c3... a→a!a→a!a→a! — — c4... a2→λ a2→λ a2→λ a →a! — c5. . . — — — — — out . . . — — — — a→a! Table 1. Function of the module FIN with strong halting state. Firing is denoted by ! rule a→a; 1 from the neuron ci4in the above mentioned module ADD, and the whole module becomes deterministic. For the latter goal, one must construct a module INPUT which would fill-in register 1 with the number of spikes corresponding to the delay between two input spikes. However, as the module ADD works in a synchronized cycle of the length three, we have to send spikes to register 1 each three computational steps (or its multiple). Otherwise the spikes might be lost (consumed) within the module ADD. The module INPUT solving this task is presented in Figure 12. One can observe that three steps after neuron i0receives the first input spike, neurons c3−c6start to fire at each step. Similarly, three steps after neuron i0 receives the second input spike, neurons c3−c6stop firing and remove all their spikes. Therefore, neuron c7will receive exactly 3nspikes, where nis the period between the first and the second input spike. Neuron c7emits one spike at each step but neuron c8lets pass only each third spike. Therefore, neuron 1 corresponding to the input register receives spikes in steps 8, 11, 14. . . , and the number of spikes is exactly n. 176 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik Fig. 11. Module FIN with simplified regular expressions and strong halting state, a version with outdegree two. Finally, observe that there are no spikes left in neurons after finishing the computation. As this is also the case in the modules ADD and SUB described in the proof of Theorem 7.1 in [8] (provided that all the registers are empty), the system halts always in the strong halting state. If we do not require strong halting, the rules a2→λin neurons c3−c6can be omitted. Therefore, the parameter forg is reduced to 1 in this case. Therefore, the described SN P system correctly simulates a register machine in the accepting mode and the inclusion NRE ⊆DSpikβ 2accP∗(rule∗ 2, cons2, forgα, dley2, outd2).The converse inclusion follows by the Church-Turing thesis. ut 6 Final Remarks In this paper we have proven the universality of SN P systems even in the situations when we have eliminated more than one of its features simultaneously. Thus, this model has been found to be computationally complete 1) when using neither delays nor forgetting rules, 2) when simplifying regular expressions and eliminating delays, 3) when using simple regular expressions and the strong halting condition and 4) when using simple regular expressions in the accepting mode. Spiking Neural P Systems: Stronger Normal Forms 177 Fig. 12. The Module INPUT with simplified regular expressions. We conjecture that in the cases 3) and 4), also delays could be removed without loss of computational universality. The case of simultaneously removing forgetting rules and simplifying regular expressions remains open but we conjecture that the universality would not be preserved in this case. In all these results one can observe a trade-off between some other computational parameters, such as the number of neurons, the maximal number of firing rules per neuron, the complexity of regular expressions, the maximum number of spikes consumed in a firing rule or the maximal number of spikes removed in a forgetting rule. In all the above mentioned cases, however, the outdegree of neurons has been bounded by two. It now remains an open problem whether these results concerning normal forms of SN P systems can be further improved. Would it be possible, for instance, to eliminate some more features of the model (three of them simultaneously) while keeping universality? If not, which would be the computational power of such a restricted model? Another open question would be, naturally, whether we can still achieve lower bounds for some of the computational parameters in our current proofs, as the number of rules in neurons, number of spikes consumed in one rule etc. 178 M. Garc´ıa-Arnau, D. P´erez, A. Rodr´ıguez-Pat´on, P. Sosik References 1. M.A. Guti´errez-Naranjo et al., eds.: Proceedings of Fourth Brainstorming Week on Membrane Computing, Febr. 2006. Fenix Editora, Sevilla, 2006. 2. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 3. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 4. W. Maass, C. Bishop, eds.: Pulsed Neural Networks, MIT Press, Cambridge, 1999. 5. M. Minsky: Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 6. Gh. P˘aun: Membrane Computing – An Introduction. Springer-Verlag, Berlin, 2002. 7. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci., 17, 4 (2006), 975–1002 8. O.H. Ibarra, A. P˘aun, Gh. P˘aun, A. Rodr´ıguez-Pat´on, P. Sos´ık, S. Woodworth: Normal forms for spiking neural P systems. In [1], Vol. II, 105-136, and Theoretical Computer Sci., 372, 2-3 (2007), 196–217. 9. Gh. P˘aun, Twenty Six Research Topics About Spiking Neural P Systems. In the present volume 10. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Salomaa: Bounding the indegree of spiking neural P systems. TUCS Technical Report 773, 2006. 11. The P Systems Web Page: http://psystems.disco.unimib.it.