Notes About Spiking Neural P Systems

Notes About Spiking Neural P Systems Mihai Ionescu1, Gheorghe P˘aun2,3 1University of Pite¸sti Str. Tˆargu din Vale, nr. 1, 110040 Pite¸sti Romania [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucharest, Romania 3Research Group on Natural Computing Department of Computer Science and AI University of Sevilla Avda Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Summary. Spiking neural P systems (SN P systems, for short) are much investigated in the last years in membrane computing, but still many open problems and research topics are open in this area. Here, we first recall two such problems (both related to neural biology) from [15]. One of them asks to build an SN P system able to store a number, and to provide it to a reader without losing it, so that the number is available for a further reading. We build here such a memory module and we discuss its extension to model/implement more general operations, specific to (simple) data bases. Then, we formulate another research issue, concerning pattern recognition in terms of SN P systems. In the context, we define a recent version of SN P systems, enlarged with rules able to request spikes from the environment; based on this version, so-called SN dP systems were recently introduced, extending to neural P systems the idea of a distributed dP automaton. Some details about such devices are also given, as a further invitation to the reader to this area of research. 1 Introduction The present notes are only an invitation to the reader to a recent and vividly investigated branch of membrane computing, inspired from the way the neurons cooperate in large nets, communicating (among others) by means of spikes, electrical impulses of identical shapes. In neural computing, this biological reality has inspired a series of research which are considered “neural computing of the third generation”, see, e.g., [5], [12]. In terms of membrane computing, the idea was captured in the form of so-called spiking neural P systems, in short, SN P systems, introduced in [10] and then investigated in a large number of papers. We refer to the Handbook [20] and to the membrane computing website [23] for details. 170 M. Ionescu, Gh. P˘aun For the reader’s convenience, we shortly recall that 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. Such a rule is of the form E/ac→ap;d, where Eis a regular expression over the alphabet {a}(adenotes the spike); such a rule can be used in a neuron if the number of spikes present in the neuron is described by the regular expression E(if there are kspikes in the neuron, then ak∈L(E), where L(E) is the regular language identified by E), and using it means consuming cspikes (hence k−cremain) and producing pspikes, which will be sent to all neurons to which a synapse exists which leaves the current neuron, after a time delay of dsteps (if d= 0, then the spikes leave immediately). If a neuron can use a rule, then it has to use one, hence the system is synchronized, in each time unit, all neurons which can spike should do it. One starts from an initial configuration and one proceed by computation steps as suggested above. One neuron is designated as the output neuron of the system and its spikes can exit into the environment, thus producing a spike train. Two main kinds of outputs can be associated with a computation in an SN P system: a set of numbers, obtained by considering the number of steps elapsed between consecutive spikes which exit the output neuron, and the string corresponding to the sequence of spikes which exit the output neuron. This sequence is a binary one, with 0 associated with a step when no spike is emitted and 1 associated with a step when a spike is emitted. Several variants were considered in the literature. We recall here the most recent one, SN P systems with request rules, proposed in [9]: also rules of the form E/λ ←arare used, with the meaning that rspikes are brought in the neuron, provided that its content is described by the regular expression E. Such rules are essentially used in defining SN dP systems, a class of distributed computing devices bridging the SN P systems area and the dP systems area – this latter one initiated in [16] and then investigated in [4], [17], [18]. We recall here the definition of SN dP systems from [9], as well an example from that paper. Also, two research topics mentioned in the last years (especially in the framework of the Brainstorming Week on Membrane Computing, organized at the beginning of each February in Sevilla, Spain – see [23]) are briefly discussed, for the first one also providing a preliminary answer (which, in turn, raises further questions). Namely, the challenge was to define a SN P module which simulate the “memory function” of the brain: stores a number, which can then be read by another “part of the brain” without losing the respective number. Such a module is provided here, but it suggests a series of continuations in terms of (simple) data bases, where several “memory cells” can be considered, loaded and interrogated, removed and added. Continuing our construction remains a task for the reader, and similarly with the second problem: to construct an SN P system able to recognize patterns, in a precise way which will be defined below. In short, this is only a quick introduction to the study of SN P systems, by giving a few basic definitions and a short list of recent notions and research topics. The interested reader should look for further details in the domain literature. Notes About SN P Systems 171 2 Formal Language and Automata Theory Prerequisites We need below only a few basic elements of automata and language theory, and of computability theory. It would be useful for the reader to have some familiarity with such notions, e.g., from [21] and [22], but, for the sake of readability we introduce here the 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 denoted by V+. When V={a}is a singleton, then we write simply a∗and a+instead of {a}∗,{a}+. If x=a1a2. . . an, ai∈V, 1≤i≤n, then mi(x) = an. . . a2a1. We denote by REG, RE the families of regular and recursively enumerable languages. The family of Turing computable sets of numbers is denoted by NRE (these sets are length sets of RE languages, hence the notation). In the rules of spiking neural P systems we use the notion of a regular expression; given an alphabet V, (i) λand each a∈Vis a regular expression over V, (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. The non-necessary parentheses can be omitted, while E+ 1∪λcan be written as E∗ 1. With each expression Ewe associate a language L(E) as follows: (i) L(λ) = {λ}, 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 any regular expressions E1, E2. The operations used here are the standard union, concatenation, and Kleene +. We also need below the operation of the right derivative of a language L⊆V∗ with respect to a string x∈V∗, which is defined by L/x ={y∈V∗|yx ∈L}. In the following sections, when comparing the power of two language generating/accepting devices the empty string λis ignored. 3 Spiking Neural P Systems with Request Rules We directly introduce the type of SN P systems we investigate in this paper; the reader can find details about the standard definition in [10], [19], [2], etc. An (extended) spiking neural P system (abbreviated as SN P system) with request rules, of 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); 172 M. Ionescu, Gh. P˘aun 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 forms (i) E/ac→ap, where Eis a regular expression over aand c≥p≥1 (spiking rules); (ii) E/λ ←ar, where Eis a regular expression over aand r≥1 (request rules); (iii) as→λ, with s≥1 (forgetting rules) such that there is no rule E/ac→ apof type (i) or E/λ ←arof type (ii) with as∈L(E); 3. syn ⊆ {1,2, . . . , m}×{1,2, . . . , m}with i6=jfor each (i, j)∈syn, 1 ≤i, j ≤m (synapses between neurons); 4. i0∈ {1,2, . . . , m}indicates the output neuron (σi0) of the system. A rule E/ac→apis applied as follows. If the neuron σicontains kspikes, and ak∈L(E), k ≥c, then the rule can fire, and its application means consuming (removing) cspikes (thus only k−cremain in σi) and producing pspikes, which will exit immediately the neuron. A rule E/λ ←aris used if the neuron contains kspikes and ak∈L(E); no spike is consumed, but rspikes are added to the spikes in σi. In turn, a rule as→λis used if the neuron contains exactly sspikes, which are removed (“forgotten”). A global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized. If a rule E/ac→aphas E=ac, then we will write it in the simplified form ac→ap. The spikes emitted by a neuron σigo to all neurons σjsuch that (i, j)∈syn, i.e., if σihas used a rule E/ac→ap, then each neuron σjreceives pspikes. The spikes produced by a rule E/λ ←arare added to the spikes in the neuron and to those received from other neurons, hence they are counted/used in the next step of the computation. If several rules can be used at the same time, then the one to be applied is chosen non-deterministically. During the computation, a configuration of the system is described by the number of spikes present in each neuron; thus, the initial configuration is described by the numbers n1, n2, . . . , nm. 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 no rule can be used. There are many possibilities to associate a result with a computation, in the form of a number (the distance between two input spikes or two output spikes) or of a string. Like in [3], we associate a symbol biwith a step of a computation when ispikes exit the system, thus generating strings over an alphabet {b0, b1, . . . , bm}, Notes About SN P Systems 173 for some m≥1. When one neuron is distinguished as an input neuron, then the sequence of symbols biassociated as above with the spikes taken from the environment by this input neuron also forms a string. In both cases, we can distinguish two possibilities: to interpret b0as a symbol or to simply ignore a step when no spike is read or sent out. The second case provides a considerable freedom, as the computation can proceed inside the system without influencing the result, and this adds power to our devices. In what follows, we also consider an intermediate case: the system can work inside for at most a given number of steps, k, before reading or sending out a symbol. (Note the important detail that this is a property of the system, not a condition about the computations: all halting computations observe the restriction to work inside for at most ksteps, this is not a way to select some computations as correct and to discard the others. This latter possibility is worth investigating, but we do not examine it here.) The obtained languages, in the accepting and the generating modes, are denoted La k(Π), Lg k(Π), respectively, where k∈ {0,1,2, . . .} ∪ {∞}. Then, Lg 0corresponds to the restricted case of [3] and Lg ∞to the non-restricted case (denoted Lλin [3]). The respective families of languages associated with systems with at most mneurons are denoted by Lα kSNPm, where α∈ {g, a}and kis as above; if k is arbitrary, but not ∞, then we replace it with ∗; if mis arbitrary, then we replace it with ∗. (Note that we do not take here into account the descriptional complexity parameters usually considered in this framework: number of rules per neuron, numbers of spikes consumed or forgotten, etc.) The computing power of the previous devices was preliminarily investigated in [9], with many questions still remaining open. We do not recall them here, but, instead, we mention the notion of a SN dP system introduced in [9]. 4 SN dP Systems We first recall from [9], without proofs, two basic results, because they provide a way to find counterexamples in this area. Actually, they are extensions to SN P systems with request rules of some results already proved in [3]. Lemma 1. The number of configurations reachable after nsteps by an extended SN P system with request rules of degree mis bounded by a polynomial g(n)of degree m. Theorem 1. If f:V+−→ V+is an injective function, card(V)≥2, then there is no extended SN P system Πwith request rules such that Lf(V) = {x f(x)|x∈ V+}=Lg ∗(Π). Corollary 1. The following two languages are not in Lg ∗SNP∗(in all cases, card(V) = k≥2): L1={x mi(x)|x∈V+}, L2={xx |x∈V+}. 174 M. Ionescu, Gh. P˘aun Note that language L1above is a non-regular minimal linear one and L2is context-sensitive non-context-free. We introduce now the mentioned distributed version of SN P systems: An SN dP system is a construct ∆= (O, Π1, . . . , Πn, esyn), where (1) O={a}(as usual, arepresents the spike), (2) Πi= (O, σi,1, . . . , σi,ki, syn, ini) is an SN P system with request rules present only in neuron σini(σi,j = (ni,j, Ri,j), where ni,j is the number of spikes initially present in the neuron and Ri,j is the finite set of rules of the neuron, 1 ≤j≤ki), and (3) esyn is a set of external synapses, namely between neurons from different systems Πi, with the restriction that between two systems Πi, Πjthere exist at most one link from a neuron of Πito a neuron of Πjand at most one link from a neuron of Πjto a neuron of Πi. We stress the fact that we allow request rules only in neurons σiniof each system Πi– although this restriction can be removed; the study of this extension remains as a task for the reader. The systems Πi,1≤i≤n, are called components (or modules) of the system ∆. As usual in dP automata, each component can take an input (by using request rules), work on it by using the spiking and forgetting rules in the neurons, and communicate with other components (along the synapses in esyn); the communication is done as usual inside the components: when a spiking rule produces a number of spikes, they are sent simultaneously to all neurons, inside the component or outside it, in other components, provided that a synapse (internal or external) exists to the destination. As above, when rspikes are taken from the environment, a symbol bris associated with that step, hence the strings we consider introduced in the system are over an alphabet V={b0, b1, . . . , bk}, with kbeing the maximum number of spikes introduced in a component by a request rule. A halting computation with respect to ∆accepts the string x=x1x2. . . xn over Vif the components Π1, . . . , Πn, starting from their initial configurations, working in the synchronous (in each time unit, each neuron which can use a rule should use one) non-deterministic way, bring from the environment the substrings x1, . . . , xn, respectively, and eventually halts. Hence, the SN dP systems are synchronized, a universal clock exists for all components and neurons, marking the time in the same way for the whole system. In what follows, like in the communication complexity area, see, e.g., [8], we ask the components to take equal parts of the input string, modulo one symbol. (One also says that the string is distributed in a balanced way. The study of the unbalanced (free) case remains as a research issue.) Specifically, for an SN dP system ∆ of degree nwe define the language L(∆), of all strings x∈V∗such that we can write x=x1x2. . . xn, with ||xi|−|xj|| ≤ 1 for all 1 ≤i, j ≤n, each component Πi of ∆takes as input the string xi,1≤i≤n, and the computation halts. Moreover, we can distinguish between considering b0as a symbol or not, like in the previous sections, thus obtaining the languages Lα(∆), with α∈ {0,1,2, . . .} ∪ {∞,∗}. Notes About SN P Systems 175 Let us denote by LαSNdPnthe family of languages Lα(∆), for ∆of degree at most nand α∈ {0,1,2, . . .} ∪ {∞,∗}. An SN dP system of degree 1 is a usual SN P system with request rules working in the accepting mode (with only one input neuron). Thus, the universality of SN dP systems is ensured, for the case of languages L∞(∆). In what follows, we prove the usefulness of distribution, in the form of SN dP systems, by proving that one of the languages in Corollary 1, can be recognized by a simple SN dP system (with two components), even working in the Lkmode. Proposition 1. {ww |w∈ {b1, b2, . . . , bk}∗} ∈ Lk+2SNdP2. Proof. The SN dP system which recognizes the language in the proposition is the following: ∆= ({a}, Π1, Π2,{((2,1),(1,3)),((1,5),(2,1))}),with the components Π1= ({a}, σ(1,1), . . . , σ(1,7), syn1,(1,1)), σ(1,1) = (3,{a3/λ ←ar|1≤r≤k} ∪ {a4a+/a →a, a4→a3}), σ(1,2) = (0,{a→a, a3→a3}), σ(1,3) = (0,{a→a, a3→a3}), σ(1,4) = (0,{a2→λ, a6→λ, a →a, a4→a}), σ(1,5) = (0,{a2→λ, a6→a, a6→a3}), σ(1,6) = (0,{a+/a →a}), σ(1,7) = (0,{a+/a →a}), syn1={((1,1),(1,2)),((1,5),(1,1)),((1,2),(1,4)),((1,4),(1,6)), ((1,4),(1,7)),((1,6),(1,7)),((1,7),(1,6)),((1,2),(1,5)), ((1,3),(1,4)),((1,3),(1,5))}, Π2= ({a}, σ(2,1),∅,(2,1)), σ(2,1) = (3,{a3/λ ←ar|1≤r≤k} ∪ {a4a+/a →a, a4→a3}). The proof that this system works properly, recognizing indeed the language in the statement of the proposition, can be found in [9]. Many problems can be formulated for SN P systems with request rules and for SN dP systems. Several were formulated in [9], from where we recall the following two general ones. :esides the synchronized (sequential in each neuron) mode of evolution, there were also introduced other modes, such as the exhaustive one, [11], and the non-synchronized one, [1]. Universality was proved for these types of SN P systems, but only for the extended case. Can universality be proved for non-extended SN P systems also using request rules? 176 M. Ionescu, Gh. P˘aun 5 Two Research Topics About SN P Systems Many research topics and open problems about SN P systems can be found in the literature. We mention here only the collection from [14], and we recall two of the problems formulated in [15]. G. Continuing with SN P systems, a problem which was vaguely formulate from time to time, but only orally, refers to a basic feature of the brain, the memory. How can this be captured in terms of SN P systems is an intriguing question. First, what means “memory”? In principle, the possibility to store some information for a certain time (remember that there is a short term and also a long term memory), and to use this information without losing it. For our systems, let us take the case of storing a number; we need a module of an SN P system where this number is “memorized” in such a way that in precise circumstances (e.g., at request, when a signal comes from outside the module), the number is “communicated” without “forgetting” it. In turn, the communication can be to only one destination or to several destinations. There are probably several ways to build such a module. The difficulty comes from the fact that if the number nis stored in the form of nspikes, “reading” these spikes would consume them, hence it is necessary to produce copies which in the end of the process reset the module. This is clearly possible in terms of SN P systems, what remains to do is to explicitly write the system. However, new questions appear related to the efficiency of the construction, in terms of time (after getting the request for the number n, how many steps are necessary in order to provide the information and to reset the module?), and also in terms of descriptional complexity (how many neurons and rules, how many spikes, how complex rules?). It is possible that a sort of “orthogonal” pair of ideas are useful: many spikes in a few neurons (nspikes in one neuron already is a way to store the number, what remains is to read and reset), or a few spikes in many neurons (a cycle of nneurons among which a single spike circulates, completing the cycle in nsteps, is another “memory cell” which stores the number n; again, we need to read and reset, if possible, using only a few spikes). Another possible question is to build a reusable module, able to store several numbers: for a while (e.g., until a special signal) a number n1is stored, after that another number n2, and so on. H. The previous problem can be placed in a more general set-up, that of modeling other neurobiological issues in terms of SN P systems. A contribution in this respect is already included in the present volume, [13], where the sleep-awake passage is considered. Of course, the approach is somewhat metaphorical, as the distance between the physiological functioning of the brain and the formal structure and functioning of an SN P system is obvious, but still this illustrates the versatility and modeling power of SN P systems. Further biological details should be considered in order to have a model with some significance for the brain study (computer simulations will then be necessary, like in the case of other applications of P systems in modeling biological processes). However, also at this formal level there are several problems to consider. For instance, what happens if the sleeping Notes About SN P Systems 177 period is shortened, e.g., because a signal comes from the environment? Can this lead to a “damage” of the system? In general, what about taking the environment into account? For instance, we can consider a larger system, where some modules sleep while other modules not; during the awake period it is natural to assume that the modules interact, but not when one of them is sleeping, excepting the case of an “emergency”, when a sleeping module can be awakened at the request of a neighboring module. Several similar scenarios can be imagined, maybe also coupling the sleep-awake issue with the memory issue. The first of these problems will be answered below. 6 A Memory Module We start by directly given the memory module which answers the requests of problem Gfrom [15]; we present it in a graphical form, in Figure 1, using the standard way of representing SN P systems (neurons as nodes of a graph, linked by arrows which represent synapses, with the rules of each neuron written in the respective nodes, together with the spikes initially present there; input and output neurons have incoming or outgoing arrows, respectively). The system in Figure 1 works as follows. The number nis introduced in the memory module, in the form of a spike train containing noccurrences of 1, one after the other. The computation starts when the first spike enters the system – at that moment, rule a5/a3→ais enabled. For the other spikes, the rule a3/a →ais used, always two spikes remaining inside neuron σ1. If no spike enters the system, then the two existing spikes are removed. If, at a subsequent step, any spike enters neuron σ1, then it is forgotten, too, by means of the rule a→λ. Thus, the number to be stored should be introduced as a compact sequence of spikes. Each input spike is doubled by neurons σ2, σ3, and in this way 2nspikes are accumulated in neuron σ4. They can stay here forever, unchanged. If the trigger neuron, σ9, receives a spike (we assume that this happens after completing the introduction of the nspikes in neuron σ1), then a further spike is sent to neuron σ4. With an odd number of spikes inside, neuron σ4consumes two by two the spikes, moving in this way nspikes in the “beneficiary” neuron σ10, at the same time moving 2nspikes to neuron σ8. Note that after exhausting the spikes of neuron σ4, one further spike is produced by σ7, hence in the end neuron σ8gets an odd number of spikes. In the same way as σ4has moved its contents to σ8, now the reverse operation takes place, hence σ4will end with 2nspikes inside (and σ8is empty). Therefore, the “cell memory” is restored, the number ncan be read again, when the trigger gets one further spike. Always, the number nis made available outside the memory module, but the module “remembers” the number, for a further usage. Now, may extensions can be imagined, for instance, towards data bases. A table in a data base can be imagined as a sequence of “memory cells” (modules), each one with its own label and value (number stored) and subject to updating