On Trace Languages Generated by Spiking Neural P Systems

On Trace Languages Generated by Spiking Neural P Systems Haiming Chen1, Mihai Ionescu2, Andrei P˘aun3, Gheorghe P˘aun4, Bianca Popa3 1Computer Science Laboratory, Institute of Software Chinese Academy of Sciences 100080 Beijing, China [email protected] 2Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial T`arraco 1, 43005 Tarragona, Spain [email protected] 3Department of Computer Science Louisiana Tech University, Ruston PO Box 10348, Louisiana, LA-71272 USA [email protected], [email protected] 4Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania, and Research Group on Natural Computing Department of Computer Science and AI University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected], [email protected] Summary. We extend to spiking neural P systems a notion investigated in the “standard” membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by “marking” it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language. 1 Introduction We continue here the study of the spiking neural P systems (in short, SN P systems) recently introduced in [7], by considering in this framework the idea of following the traces of an object through the system in order to get a language. 208 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa For usual P systems (with symport/antiport rules), this way of generating a language was introduced in [6] and then investigated in a series of papers (see, e.g., [3] and Section 4.4 of [9]). In short, an SN P system consists of a set of neurons placed in the nodes of a graph and sending signals (spikes) along synapses (edges of the graph), under the control of firing rules. One also uses forgetting rules, which remove spikes from neurons. Therefore, the spikes are moved, created, destroyed, but never modified (there is only one type of objects in the system). This makes possible and natural to distinguish one of the spikes present already in the initial configuration of the system and to follow its path through the neurons, recording the labels of the neurons and thus obtaining a string. More precisely, we assume that one of the spikes has a “flag”, which remains with this spike as long as the spike is not consumed or forgotten, but the flag passes to the produced spike when the old holder is consumed; the flag disappears when the spike is forgotten or sent out of the system. More precise definitions will be given in Section 3. We only add here the fact that we consider only halting computations, so that the labels of neurons visited by the flag form a string; due to the non-determinism in the SN P system functioning, we get in this way a set of strings, hence a language, associated with the system. Because the SN P systems are Turing complete as number computing devices (see [7] and [10]) and also complete modulo direct and inverse morphisms in the case when they are used as language generators (see [1]), it is expected that the SN P systems are powerful also as trace languages generators. This expectation is somewhat confirmed below: we both produce a series of examples of systems with an intricate functioning, we give a representation of regular languages (over any alphabet), and we also show that unary recursively enumerable languages have simple representations in terms of SN P systems trace languages. On the other hand, because of the specific way the trace language is generated, there are finite (even singleton) languages which cannot be obtained in this way. However, due to the preliminary stage of our research, we do not have yet a precise estimation of the size of the generated families of languages; many problems in this respect are formulated along the paper. In all these investigations we try to keep the used system as simple as possible, with respect to the many descriptional complexity measures which can be considered for SN P systems: number of neurons, number of rules in each neuron, number of consumed or forgotten spikes in each rule, etc. 2 Formal Language Theory Prerequisites We assume the reader to be familiar with basic language and automata theory, e.g., from [11] and [12], so that we introduce here only some notations and notions used later in the paper. For an alphabet V,V∗denotes the set of all finite strings of symbols from V; the empty string is denoted by λ, and the set of all nonempty strings over Vis On Trace Languages Generated by Spiking Neural P Systems 209 denoted by V+. When V={a}is a singleton, then we write simply a∗and a+ instead of {a}∗,{a}+. A morphism h:V∗ 1−→ V∗ 1such that h(a)∈ {a, λ}for each a∈V1is called projection, and a morphism h:V∗ 1−→ V∗ 2such that h(a)∈V2∪ {λ}for each a∈V1is called a weak coding; it is a coding if h(a)∈V2for all a∈V1. If L1, L2⊆V∗are two languages, the left and right quotients of L1with respect to L2are defined by L2\L1={w∈V∗|xw ∈L1for some x∈L2}, and respectively L1/L2={w∈V∗|wx ∈L1for some x∈L2}. When L2is a singleton, L2={x}, we write ∂l x(L1) for {x}\L1and ∂r x(L1) for L1/{x}, and we call these operations left and right derivatives of L1with respect to x. A Chomsky grammar is given in the form G= (N, T, S, P), where Nis the nonterminal alphabet, Tis the terminal alphabet, S∈Nis the axiom, and Pis the finite set of rules. For regular grammars, the rules are of the form A→aB, A →a, for some A, B ∈N, a ∈T. We ignore here the empty string and this convention is assumed in the paper always when examining the generative power of any device. We denote by F IN, REG, CF, CS, RE the families of finite, regular, contextfree, context-sensitive, and recursively enumerable languages; by MAT we denote the family of languages generated by matrix grammars without appearance checking ([11], [2]). 3 Trace Languages Associated with Spiking Neural P Systems We introduce first the SN P systems in their basic form, then we define the new way of using them, as (trace) language generators; for further details we refer to [7], [10]. Aspiking neural P system (abbreviated as SN P system), of degree m≥1, is a construct of the form Π= (O, σ1,...,σm, syn), 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/ac→a;d, where Eis a regular expression over a,c≥1, and d≥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); 210 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa 3. syn ⊆ {1,2,...,m} × {0,1,2,...,m}with i6=jfor each (i, j)∈syn, 1 ≤ i, j ≤m(synapses between neurons), with 0 indicating the environment of the system. Note that, in contrast to [7], we have not indicated here an output neuron, but we have allowed synapses (i, 0) for any neuron σi; actually, in the trace case investigated here we do not really need such synapses, but we consider them just because such links with the environment are “realistic”. The rules of type (1) are firing (we also say spiking)rules, and they are applied as follows. If the neuron σicontains kspikes, and ak∈L(E), k ≥c, then the rule E/ac→a;dcan be applied. The application of this rule means consuming (removing) cspikes (thus only k−cremain in σi), the neuron is fired, and it produces a spike after dtime units (a global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized). If d= 0, then the spike is emitted immediately, if d= 1, then the spike is 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 again open, so that it can receive spikes (which can be used starting with the step t+d+ 1), but it does not use any rule at this step (the neuron is busy with sending out the spike it has produced dsteps before and stored up to now inside). A spike emitted by a neuron σi(is replicated and a copy of it) goes to each neuron σjsuch that (i, j)∈syn, as well as to the environment, if (i, 0) ∈syn. (When a neuron σiemits a spike and there is no neuron to receive it, then a synapse (i, 0) is used as an explicit way to point out that the spike is “lost” in the environment.) The rules of type (2) are forgetting rules and they are applied as follows: if the neuron σicontains exactly sspikes, then the rule as→λfrom Rican be used, meaning that all sspikes are removed from σi. If a rule E/ac→a;dof type (1) has E=ac, then we will write it in the simplified form ac→a;d. In each time unit, if a neuron σican use one of its rules, then a rule from Ri must be used. Since two firing rules, E1/ac1→a;d1and E2/ac2→a;d2, can have L(E1)∩L(E2)6=∅, it is possible that two or more rules can be applied in a neuron, and in that case, only one of them is chosen non-deterministically. By definition, if a firing rule is applicable, then no forgetting rule is applicable, and vice versa. The initial configuration of the system is described by the numbers n1, n2,...,nm, of spikes present in each neuron, with all neurons being open. During the computation, a configuration is described by both the number of spikes present in each neuron and by the state of the neuron, more precisely, by the number of steps from now on until it becomes open (this number is zero if the neuron is already open). Thus, hr1/t1,...,rm/tmiis the configuration where neuron i= 1,2,...,m contains ri≥0 spikes and it will be open after ti≥0 steps; with this notation, the initial configuration is C0=hn1/0,...,nm/0i. On Trace Languages Generated by Spiking Neural P Systems 211 Using the rules as described above, one can define transitions among configurations. A transition between two configurations C1, C2is denoted by C1=⇒C2. 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. In the spirit of spiking neurons, see, e.g., [8], as the result of a computation, in [7] and [10] one considers the distance between two consecutive spikes which exit a distinguished neuron of the system. Then, in [1] one considers as the result of a computation the so-called spike train of the computation, the sequence of symbols 0 and 1 obtained by associating 1 with a step when a spike exits the system and 0 otherwise. Languages over the binary alphabet are computed in this way. Here we consider yet another idea for defining a language, taking into account the traces of a distinguished spike through the system. Specifically, we distinguish one of the neurons of the system as the input one (thus, we add a further component, in, to the system description, with in ∈ {1,2,...,m}) and in the initial configuration of the system we “mark” one spike from this neuron – the intuition is that this spike has a “flag” – and we follow the path of this flag during the computation, recording the labels of the neurons where the flag is present in the end of each step. Actually, for neuron σiwe consider the symbol biin the trace string. (When presenting the initial configuration of the system, the number nin, of spikes present in the input neuron, is written in the form n′ in, to indicate that the marked spike is here.) The previous definition contains many delicate points which need clarifications – and we use a simple example to do this. Assume that in neuron σiwe have three spikes, one of them marked; we write aaa′to represent them. Assume also that we have a spiking rule aaa/aa →a; 0. When applied, this rule consumes two spikes, one remains in the neuron and one spike is produced and sent along the synapses going out of neuron σi. Two cases already appear: the marked spike is consumed or not. If not consumed, it remains in the neuron. If consumed, then the flag passes to the produced spike. Now, if there are two or more synapses going out of neuron σi, then again we can have a branching: only one spike is marked, hence only on one of the synapses (i, j) we will have a marked spike and that synapse is non-deterministically chosen (on other synapses we send non-marked spikes). If σjis an open neuron, then the marked spike ends in this neuron. If σjis a closed neuron, then the marked spike is lost, and the same happens if j= 0 (the marked spike exits in the environment). Anyway, if the marked spike is consumed, at the end of this step it is no longer present in neuron i; it is in neuron σjif (i, j)∈syn and neuron σjis open, or it is removed from the system in other cases. Therefore, if in the initial configuration of the system neuron σicontains the marked spike, then the trace can start either with bi(if the marked spike is not consumed) or with bj(if the marked spike was consumed and passed to neuron σj); if the marked spike is consumed and lost, then we generate the empty string, which is ignored in our considerations. Similarly in later steps. 212 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa If the rule used is of the form aaa/aa →a;d, for some d≥1, and the marked spike is consumed, then the newly marked spike remains in neuron σifor dsteps, hence the trace starts/continues with bd i. Similarly, if no rule is used in neuron σi for ksteps, then the trace records kcopies of bi. If a forgetting rule is used in the neuron where the marked spike is placed, then the trace string stops (and no symbol is recorded for this step). Therefore, when considering the possible branchings of the computation, we have to take into account the non-determinism not only in using the spiking rules, but also in consuming the marked spike and in sending it along one of the possible synapses. The previous discussion has, hopefully, made clear what we mean by recording the labels of the neurons where the flag is present in the end of each step, and why we have chosen the end of a step and not the beginning: in the latter case, all traces would start with the same symbol, corresponding to the input neuron, which is a strong – and artificial – restriction. In the next section, we will illustrate all these points by a series of examples. Anyway, we take into account only halting computations: irrespective whether or not a marked spike is still present in the system, the computation should halt (note that it is possible that the marked spike is removed and the computation still continues for a while – but this time without adding further symbols to the trace string). For an SN P system Πwe denote by T(Π) the language of all strings describing the traces of the marked spike in all halting computations of Π. Then, we denote by TSNPm(rulek, consp, forgq) the family of languages T(Π), generated by systems Πwith at most mneurons, each neuron having at most krules, each of the spiking rules consuming at most pspikes, and each forgetting rule removing at most q spikes. As usual, a parameter m, k, p, q is replaced with ∗if it is not bounded. 4 Examples We consider here several examples, both illuminating the previous definitions and relevant for the intricate work of SN P systems as language generators by means of traces; indications on the power of these devices are also obtained in this way. We start with a system already having a complex behavior, the one whose initial configuration is given in Figure 1 (we denote it by Π1). This also gives us the opportunity to introduce the way to graphically represent an SN P system: as a directed graph, with the neurons as nodes and the synapses indicated by arrows; in each neuron we give the rules and the spikes present in the initial configuration, with the marked spike indicated by a prime; synapses of the form (i, 0) are indicated by arrows pointing to the environment. We have three neurons, labeled with 1, 2, 3, with neuron σ1being the input one. Each neuron contains three rules, and only neuron σ1has two spiking rules, but the non-determinism of the system is considerable, due to the possible traces of the marked spike. On Trace Languages Generated by Spiking Neural P Systems 213 ' & $ % ' & $ % ' & $ % -         A A A A AK AAAAAAA AU 21 a3 a3/a2→a; 0 a2→λ a→λ a3/a2→a; 0 aaa′ a3/a2→a; 1 a→λ 3 a3 a3/a2→a; 0 a2→λ a→λ Fig. 1. The initial configuration of system Π1 The evolution of the system Π1can be analyzed on a transition diagram as that from Figure 2: because the number of configurations reachable from the initial configuration is finite, we can place them in the nodes of a graph, and between two nodes/configurations we draw an arrow if a direct transition is possible between them. It should be noted in Figure 2 an important detail: when presenting a configuration of the system where there is a marked spike, it is no longer sufficient to indicate only the number of spikes and the open status of neurons, but we also have to indicate the place of the marked spike (if the system still contains such a spike). This is done by priming either the number of spikes from the neuron where the marked spike is, or by priming the number of steps until the neuron is open, in the case when a marked spike was produced by means of a spiking rule with delay. In Figure 2 we have also indicated on the arrows the symbol introduced in the trace string by that arrow (this is bj, where σjis the neuron where the marked spike arrives in the end of this step). Thus, following the marked arrows, we can construct the language of all traces. Let us follow on this diagram some of the possible traces. As long as neuron σ1 uses the rule a3/a2→a; 0, the marked spike circulates among neurons σ1, σ2, σ3 and the computation continues. Note that the marked spike can be consumed or not; in the first case it moves to one of the partner neurons, non-deterministically chosen, in the latter case it remains in the neuron where it is placed. 214 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa h0/0,0/0,0/0i h1′/0,1/0,1/0ih1/0,1/0,1/0i h1/0,1′/0,1/0i h1/0,1/0,1′/0i h1′/1,2/0,2/0i h1/1′,2/0,2/0i h1/1,2′/0,2/0ih1/1,2/0,2′/0i h3′/0,3/0,3/0i h3/0,3′/0,3/0i h3/0,3/0,3′/0i ^Us /N ? ? ss? qR/) ~ } ~ I    ? ? ? -U / b3 b1 b1b3 b2 b2 b1 b3 b2 b3 b3 b2 b2 b1 b1 b1b2b3 Fig. 2. The transition diagram of system Π1 When neuron σ1uses the rule a3/a2→a; 1, then the computation passes to the halting phase – in the diagram from Figure 2, we leave the upper level and we pass to the next level of configurations. If the marked spike was in neuron σ1, it is or not consumed; this is the case when reaching the configurations h1′/1,2/0,2/0i, h1/1′,2/0,2/0i: all neurons consume two spikes, but neurons σ2and σ3exchange one spike, hence they end the step with two spikes inside; neuron σ1has only one spike inside (it is closed, does not accept spikes from neurons σ2and σ3) and one ready to be emitted, and either one of them can be the marked one. In each case, after two more steps the computation halts with no spike in the system. Thus, the traces start with an arbitrary string xover {b1, b2, b3}, and end with one of the strings b1b1, b1b2, b1b3, b2, b3, depending on the last symbol of x. On Trace Languages Generated by Spiking Neural P Systems 215 # " ! # " ! ' & $ %    - 6 6 1 2 34 aaa′ a3/a2→a; 0 a2→λ a2→λ a a→a;n−1 a a→a;m−1 Fig. 3. The initial configuration of system Π2 We continue with two simpler examples, not devoid of interest: in search for counterexamples, we have tried several finite languages, and for many of them the result was that in all cases it was possible to find an SN P system to generate these languages. We continue to present these systems in a graphical form instead of giving them formally, because the figures are much easier to understand. ' & $ % ' & $ % -  12 aaaa′ a4/a2→a; 0 a2→a; 0 a2 a3→a; 0 Fig. 4. The initial configuration of system Π3 The two examples are given in Figures 3, 4, and the respective systems are denoted by Π2, Π3, respectively. The system Π2from Figure 3 generates the language T(Π2) = {bn 1, bm 2}, for n, m ≥1. In the first step, neuron σ1consumes or does not consume the marked spike, thus keeping it inside or sending it to neuron σ2. One spike remains in neuron σ1and one is placed in neuron σ2. Simultaneously, neurons σ3and σ4fire, and they spike after n−1 and m−1 steps, respectively. Thus, in steps nand m, neurons σ1and σ2, respectively, receive one more spike, which is forgotten in the next step together with the spike existing there. Note that nand mcan be equal or different. For the system in Figure 4 we have T(Π3) = {b1b2, b2b1}– we leave the task to check this equality to the reader. 222 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa Theorem 6. Every unary language L∈RE can be written in the form L= h(L′) = (d∗ 1\L′)∩d∗ 2, where L′∈TSNP∗(rule2, cons3, forg3), and his a projection. Proof. This result is a consequence of the fact that SN P systems can simulate register machines. Specifically, as proved in [7], starting from a register machine M(we do not need precise definitions and notations; details about register machines can be found in many books), we construct an SN P system Πwhich halts its computation with 2nspikes in a specified neuron σout if and only if ncan be generated by the register machine M; in the halting moment, a neuron σlhof Π associated with the label of the halting instruction of Mgets two spikes and fires. The neuron σout contains no rule used in the simulation of M(the corresponding register is only incremented, but never decremented – see the details of the construction from [7]). Now, consider a language L⊆b∗ 2, L ∈RE. There is a register machine M such that n∈N(M) if and only if bn 2∈L. Starting from such a machine M, we construct the system Πas in [7], having the properties described above. We append to the system Πsix more neurons, as indicated in Figure 7. There is a marked spike in neuron σ1, and it will stay here during all the simulation of M. In the moment when neuron σlhof Πspikes, its spike goes both to neuron σout and to neuron σ1. Neurons σ3, σ4, σ5, σ6play the same role as neurons σ6, σ9, σ10, σ12 in the system from Figure 6, namely to send a spike to neuron σ2only when neuron σout has finished its work (this happens after nsteps of using the rule a(aa)+/a2→a; 0, for 2nbeing the contents of neuron σout in the moment when neuron σlhspikes). The marked spike leaves neuron σ1four steps after using the rule a2→a; 4, hence five steps after the spiking of neuron σlh. This means that the marked spike waits in neuron σ2exactly nsteps. When the spike of neuron σ6reaches neuron σ2, the two spikes present here, the marked one included, are forgotten. Thus, the traces of the marked spike are of the form br 1bn 2, for some r≥1 and n∈N(M). By means of the left derivative with the regular language b∗ 1we can remove prefixes of the form bk 1and by means of the intersection with b∗ 2we ensure that the maximal prefix of this form is removed. Similarly, the projection h:{b1, b2}∗−→ {b1, b2}∗defined by h(b1) = λ,h(b2) = b2, removes all occurrences of b1. Consequently, L= (b∗ 1\T(Π)) ∩b∗ 2=h(T(Π)). The system Πfrom [7] (Theorem 7.1 there) has the rule complexity described by rule2, cons3, forg3; one sees that the construction from Figure 7 does not increase these parameters. In what concerns the number of neurons, we do not have a bound for the language L′from the previous theorem. Corollary 1. Each family TSNP∗(regk, consp, forgq)with k≥2, p ≥3, q ≥3, is incomparable with each family of languages FL which contains the singleton languages, is closed under left derivative with regular languages and intersection On Trace Languages Generated by Spiking Neural P Systems 223      ' & $ %          ' & $ % ' & $ %     ? ? ? ? ? -   = SS Sw Π out a(aa)+/a2→a; 0 lh a2→a; 0 a→λ 1 a′ a2→a; 4 2 a2→λ a→a; 0 3 4 a→a; 0 5 a(aa)∗/a →a; 0 6 a2→a; 0 Fig. 7. The SN P system from the proof of Theorem 6 with regular languages, and does not contain all unary recursively enumerable languages. Families as above are FIN, REG, CF, CS, MAT etc. (every one-letter language in MAT is regular, see [4]). 6 Final Remarks We have considered here the possibility of generating a language by means of a spiking neural P system by following the traces of a distinguished spike during a halting computation. The power of such devices seems to be rather large – Theorem 6 – but we do not have a precise characterization of the obtained families of languages. Theorem 6 also raises the natural question whether RE languages over arbitrary alphabets can be represented starting from trace languages of SN P systems. 224 H. Chen, M. Ionescu, A. P˘aun, Gh. P˘aun, B. Popa The main difficulty in handling the trace languages of SN P systems is, in the previous setup, the non-determinism of the marked spike evolution. A possible way to better control the marked spike is to consider spiking rules of the forms E′/ac→a;dand E/a′ac→a′;d, with the meaning that the prime indicates whether or not the rule consumes the marked spike: this is not the case when the prime is attached to E, but this happens if the prime marks one of the consumed spikes, and hence also the produced spike. This removes the non-determinism induced by the use of the marked spike when applying the rules, but still nondeterminism remains in what concerns the choice of synapses towards neighboring neurons (and this was the basis of the easy counterexample from Theorem 1). How also this non-determinism can be removed remains as a research topic. 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. In the present volume. 2. J. Dassow, Gh. P˘aun: Regulated Rewriting in Formal Language Theory. SpringerVerlag, Berlin, 1989. 3. P. Frisco. H.J. Hoogeboom: Simulating counter automata by P systems with symport/antiport. In Membrane Computing. International Workshop, WMC 2002, Curtea de Arge¸s, Romania, August 2002. Revised Papers (Gh. P˘aun, G. Rozenberg, A. Salomaa, C. Zandron, eds.), LNCS 2597, Springer-Verlag, Berlin, 2003, 288–301. 4. D. Hauschild, M. Jantzen: Petri nets algorithms in the theory of matrix grammars. Acta Informatica, 31 (1994), 719–728. 5. O.H. Ibarra, A. P˘aun, Gh. P˘aun, A. Rodr´ıguez-Pat´on, P. Sosik, S. Woodworth: Normal forms for spiking neural P systems. In volume II of the present proceedings. 6. M. Ionescu, C. Martin-Vide, A. P˘aun, Gh. P˘aun: Membrane systems with symport/antiport: (unexpected) universality results. In Proc. 8th International Meeting of DNA Based Computing (M. Hagiya, A. Ohuchi, eds.), Japan, 2002, 151–160. 7. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 8. W. Maass: Computing with spikes. Special Issue on Foundations of Information Processing of TELEMATIK, 8, 1 (2002), 32–36. 9. Gh. P˘aun: Membrane Computing – An Introduction. Springer-Verlag, Berlin, 2002. 10. Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg: Spike trains in spiking neural P systems. Intern. J. Found. Computer Sci., to appear (also available at [13]). 11. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages, 3 volumes. SpringerVerlag, Berlin, 1997. 12. A. Salomaa: Formal Languages. Academic Press, New York, 1973. 13. The P Systems Web Page: http://psystems.disco.unimib.it.