Spiking Neural dP Systems

Spiking Neural dP Systems Mihai Ionescu1, Gheorghe P˘aun2,3, Mario J. P´erez-Jim´enez3, Takashi Yokomori4 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], [email protected] 4Department of Mathematics, School of Education Waseda University, 1-6-1 Nishi-waseda, Shinjuku-ku Tokyo 169-8050, Japan [email protected] Summary. We bring together two topics recently introduced in membrane computing, the much investigated spiking neural P systems (in short, SN P systems), inspired from the way the neurons communicate through spikes, and the dP systems (distributed P systems, with components which “read” strings from the environment and then cooperate in accepting their concatenation). The goal is to introduce SN dP systems, and to this aim we first introduce SN P systems with the possibility to input, at their request, spikes from the environment; this is done by so-called request rules. A preliminary investigation of the obtained SN dP systems (they can also be called automata) is carried out. As expected, request rules are useful, while the distribution in terms of dP systems can handle languages which cannot be generated by usual SN P systems. We always work with extended SN P systems; the non-extended case, as well as several other natural questions remain open. 1 Introduction We combine here two ideas recently considered in membrane computing, the spiking neural P systems (in short, SN P systems) introduced in [9], and the dP systems introduced in [13]. 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) 194 M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori along synapses (edges of the graph), under the control of firing rules. 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. Actually, we use extended SN P systems, that is, we allow rules of the form E/ac→ap, with the following meaning: if the content of the neuron is described by the regular expression E, then cspikes are consumed and pare produced and sent to the neurons to which there exist synapses leaving the neuron where the rule is applied (more precise definitions will be given in Section 3). In this way, strings over arbitrary alphabets can be obtained: if ispikes are sent out at the same time, then we say that the symbol biwas generated. The languages generated by SN P systems in this way were investigated in [2] and [3]; see also [4]. In turn, a dP systems consists of several “modules” (usual P systems), which communicate among them by means of antiport rules like in tissue P systems. When only symport/antiport rules are used inside modules, then we can define a language accepted by such a system: each component takes from the environment sequences of symbols, they work separately and communicate through antiport rules and, if the computation halts, then the concatenation of the input strings is accepted. See [6], [13], [15], [16] for a series of results about such machineries; in particular, [6] investigates the language families characterized by P and dP automata, their relationships and place in Chomsky hierarchy. There is an apparent difference between the two classes of P systems: SN P systems generate strings, while dP systems accept them. There were considered SN P systems also working in the accepting mode, with a spike train (a number is encoded as the distance between two consecutive spikes) introduced in a specified neuron of the system in the first steps of the computation. However, a more natural way to proceed, more similar to the way the P automata take symbols from the environment, is to consider a new type of rules in SN P systems, able to take spikes from the environment. We consider such rules of a form rather similar to spiking rules, namely, of the form E/λ ←ar: if the contents of the neuron is described by the regular expression E, then rspikes are brought from the environment. Such a rule can be applied as a usual spiking rule (its use lasts one time unit, with the spikes brought from the environment being added to the contents of the neuron and ready to be used in the next step). Now, the definition of an SN P system with request rules is rather natural: the neurons which contain request rules are supposed as having a “synapse” also with the environment such that they can take spikes from the environment, depending on the number of spikes they contain. The computation proceeds as usual, starting from the initial configuration. Both input and output spike trains can be associated with the neurons linked with the environment. Also the step to SN dP systems Spiking Neural dP Systems 195 (we can call them automata) is natural: take “modules” (or components) consisting of neurons, with only one neuron of each component also having a synapse with the environment (hence able to take an input); each component can be linked with another component through synapses among their neurons (for simplicity, we consider only the case when at most one synapse is available in each direction). The components take strings from the environment and the concatenation of these strings is accepted if the computation of the system halts. Many questions arise in this framework. Compare usual SN P systems with SN P systems having request rules, both in the generative and the accepting mode. Do the additional facilities provided by the request rules help, e.g., from the point of view of the descriptional complexity? What about imposing a bound on the environment (considering that in the beginning it only contains a given number of spikes, and further spikes can be there only if the system sends spikes out)? More interesting: which is the power of SN dP systems? As expected, it is larger than that of SN P systems (with the mentioning that we compare languages accepted by SN dP systems with languages generated by SN P systems). In this context, we introduce a refinement in the way of defining languages associated with (extended) SN P systems. In between the restricted (in each step, one symbol is produced) and the non-restricted case we can consider the languages generated/accepted in the k-restricted way: between reading or producing two symbols which are considered in the string, the system can work at most ksteps without reading or sending symbols out. 2 Formal Language and Automata Theory Prerequisites We assume the reader to be familiar with basic language and automata theory, e.g., from [18] and [19], 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 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 most universality proofs in membrane computing, in particular, in the SN P systems area, one uses register machines (several registers can contain natural numbers; they are increased by one or decreased by one – the latter operation only after checking whether the number stored in the register is different from zero –, by means of labeled instructions; if the computation starting in an initial label with all registers empty halts by reaching a special halting label, then the number stored in the halting configuration by the first register is said to be computed/generated by that computation. 196 M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori Because our SN P systems can read at the same time several spikes, an operation which corresponds to reading a symbol from an alphabet with several elements, we will use in the universality proof a device more adequate to this case: counter automata with an input tape. The version we choose is one with as simple as possible instructions: check for zero, increment, decrement (by one in both cases), read a symbol from the input tape, halt. Formally, such a device is a construct M= (n, V, H, l0, lh, I), where nis the number of registers/counters, Vis the alphabet of the input tape, His the set of labels, each one uniquely associated with an instruction, l0is the initial label, lhis the halt label, and Iis the set of instructions of the following forms: 1. (li:check(r), lj, lk): when label liis reached, the contents of register ris compared to zero; if the register is empty, then the next label is lj, if the contents of the register is strictly positive, then the next label is lk; 2. (li:add(r), lj): add 1 to the contents of register rand pass from label lito label lj; 3. (li:sub(r), lj): subtract 1 from the contents of register rand pass from label li to label lj(the operation is supposed to be possible, meaning that previously the register was checked for zero by an instruction of the first type); 4. (li:read(b), lj): read the symbols b∈Vfrom the tape and pass from label li to label lj; 5. lh:halt: when reaching lh, the computation halts; this is the only instruction labeled by lh. Without loss of the generality, we may assume that in all instructions the involved labels are mutually different (this can be easily achieved by introducing intermediate labels, involved in additional instructions performing “dummy” operations, of the form “add 1 to register r, then subtract 1 from register r”. We start with label l0(by applying the instruction with label l0), with all counters empty (storing the number 0), with the “reading head” in front of the first symbol of the input tape, where a string is written. We proceed as specified by the instructions, under the control of labels. The process is deterministic and the only branching is based on the check for zero of the registers. When the label lh(hence the instruction lh:halt) is reached, the computation stops and the sequence of symbols read from the input tape is the string accepted by the counter machine. The language of all such strings is denoted by L(M). It is known that counter machines (with a small number of counters, but this is not of interest below) with an input tape can recognize all recursively enumerable languages. Details (variants and proofs) can be found in several places: [11], [5], [7]. In the following sections, when comparing the power of two language generating/accepting devices the empty string λis ignored. Spiking Neural dP Systems 197 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 [9], [14], [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); 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. 198 M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori 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}, 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.) By the definitions, we have the following inclusions for all β∈ {1,2, . . .} ∪ {∗}: Lα 0SNPβ⊆Lα 1SNPβ⊆Lα 2SNPβ⊆. . . Lα ∗SNPβ⊆Lα ∞SNPβ⊆RE. 4 Some Preliminary Results for the Generating Case In general, the results which were obtained for SN P systems without request rules are expected to hold – maybe with simplified proofs – also for SN P systems with request rules. However, some differences exist. For instance, it is observed in Spiking Neural dP Systems 199 [2] that the language {0,1}cannot be generated by an SN P system (the output neuron cannot choose between spiking or not spiking in the first step), but this language can be generated by the system ({a},(1,{a→a, a/λ ←a}),∅,1), because of the possibility of choosing between spiking or bringing a spike inside (the system halts after the first step). However, this is mainly due to the definition – allowing a nondeterministic choice between spiking and forgetting rules will lead to a similar result also for SN P systems without request rules. Returning to the extension of results to the new class of SN P systems, we consider here three results from [3], as they are significant below. 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. Proof. The same as in [3], with the observation that the number of spikes in the system is increased in two cases: when a neuron spikes, hence it introduces a well defined number of spikes in all neurons with which it has synapses, or when it brings spikes from the environment; in this case, the spikes, again a well defined number, are introduced in the neuron which has used the request rule. The rest of the argument remains the same as in [3]. ut 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 ∗(Π). Proof. Assume that there is an extended SN P system Πof degree m, with request rules, such that Lg k(Π) = Lf(V) for some fand Vas in the statement of the theorem and some k≥1. According to the previous lemma, there are only polynomially many configurations of Πwhich can be reached after nsteps. Take some nof the form n=km. The string generated after nsteps is of length at least m. However, there are card(V)m≥2m= 2n/k strings of length min V+. Therefore, for large enough mthere are two strings w1, w2∈V+, w16=w2, such that after nsteps the system Πreaches the same configuration when generating the strings w1f(w1) and w2f(w2), hence after step nthe system can continue any of the two computations. This means that also the strings w1f(w2) and w2f(w1) are in Lg k(Π). Due to the injectivity of fand the definition of Lf(V) such strings are not in Lf(V), hence the equality Lf(V) = Lg k(Π) is contradictory. ut 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+}. 200 M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori Note that language L1above is a non-regular minimal linear one and L2is context-sensitive non-context-free. Theorems 3 and 4 from [3] (characterizing regular languages, modulo a symbol added to their strings), and Theorem 5 (generating non-semilinear languages), always in the restricted mode, can now be written in the form: Theorem 2. Lg ∞SNP2⊆REG ⊂Lg 1SNP3. 5 The Accepting Case In order to have a definition of the language accepted by a given SN P system with request rules, we have to distinguish a neuron as the input one, and only the sequence of symbols taken from the environment by that neuron is introduced in the language. The other neurons are allowed to bring spikes from the environment, but those spikes are not defining symbols for the processed string. First, let us notice that Lemma 1 and Theorem 1 remains true also in the accepting case, hence the languages in Corollary 1 cannot be recognized. Also the characterization of RE from [3] remains true. However, this proof is rather complex: one takes symbols from the environment, in the form of packages of spikes, but for a string wover an alphabet with ksymbols, one passes to valk+1(w), the numerical value of wwhen considered as a number written in base k+ 1, and one accepts wif and only if valk+1(w) is accepted (a language Lis in RE if and only if valk+1(L) is in NRE). Then, handling numbers is reduced to simulating register machines (basically, counter machines without an input tape). Here we will proceed in a direct way, proving that SN P systems with request rules can recognize all RE languages by starting from counter automata with input tape. Theorem 3. La ∞SNP∗=RE. Proof. Let us consider a counter automaton M= (n, V, H, lo, lh, I) as introduced in Section 2, with V={b1, . . . , bk}. We construct modules simulating instruction of the first four types mentioned in Section 2 – no halting module is necessary, we just ignore the halting instruction. Let us denote by Πthe SN P system we construct. For each counter rof M,Πcontains a neuron σr,1≤r≤n; if the value of the counter will be at some moment m, then the associated neuron will contain 2m spikes. For each label l∈H, we also introduce in Πa neuron σl. All neurons of the system are empty in the beginning of the computation, except neuron σl0, which contains one spike. Having a spike inside, this neuron is active; in general, when a neuron σl, l ∈H, receives one spike, then it is active, the associated module will start working, simulating the instruction identified by the label l. There is a unique input neuron, with the label in, and σin is the only neuron of Πwhich contains request rules. Several other auxiliary neurons are involved in the modules. They and the synapses among all these neurons are specified below. Spiking Neural dP Systems 201 We do not give formally the modules, but in a graphical form. Let us start with a CHECK instruction, (li:check(r), lj, lk). We construct the module shown in Figure 1. ¶ µ³ ´¶ µ³ ´ ' & $ % ' & $ % ¶ µ³ ´¶ µ³ ´ ¶ µ³ ´ ¶ µ³ ´ ¶ µ³ ´ ¶ µ³ ´ ' & $ % º ¹· ¸ ¡ ¡ ¡ª HHH Hj ¶ ¶ ¶/ JJ J^ @@@@R ?   À ¶ ¶ ¶ ¶ ¶/ @@@@R HHHHHHHHH Hj C C C CO ¡¡¡ ¡µ 6 Q Q Q Qk ?? li a→a a1 a→ar a(aa)+/a3→a a→λ a2 a→a a3 a→a a4 a→a a5 a→a a6 a→a a7 a→λ a2→a a3→λa8 a→λ a2→a ljlk Fig. 1. The CHECK module As long as the contents of a neuron σris an even number, no rule can be applied in it. If σlibecomes active, it sends a spike to σr, hence the number of spikes becomes odd. If this number is 1, hence the counter was empty, then a spike will eventually arrive in σlj. If the counter was non-zero, then only σa8will spike. In this way, it activates the neuron σlkand also restores the contents of counter r, putting back the two spikes consumed by the rule a(aa)+/a3→a. The continuation is correct in both cases. The new neurons, σas,1≤s≤8, are uniquely associated with this module (it would be more rigorous to label them, say, by (li, s),1≤s≤8, but we prefer the simple writing). All the three label neurons in Figure 1 can have incoming synapses from various other neurons, but each such neuron has only one associated module which is triggered by it. These remarks are valid for all modules constructed below. Because several CHECK instructions (also several SUB instructions – see below) can act on the same counter r, it means that σrcan have synapses to several 208 M. Ionescu, Gh. P˘aun, M.J. P´erez-Jim´enez, T. Yokomori 6. R. Freund, M. Kogler, Gh. P˘aun, M.J. P´erez-Jim´enez: On the power of P and dP automata. Annals of Bucharest University. Mathematics-Informatics Series, 63 (2009), 5–22. 7. J.E. Hopcroft, J.D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, Mass., 1979. 8. J. Hromkovic: Communication Complexity and Parallel Computing: The Application of Communication Complexity in Parallel Computing. Springer, Berlin, 1997. 9. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems. Fundamenta Informaticae, 71, 2-3 (2006), 279–308. 10. M. Ionescu, Gh. P˘aun, T. Yokomori: Spiking neural P systems with exhaustive use of rules. Intern. J. Unconventional Computing, 3, 2 (2007), 135–154. 11. M. Minsky: Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 12. Gh. P˘aun: Membrane Computing. An Introduction. Springer, Berlin, 2002. 13. Gh. P˘aun, M.J. P´erez-Jim´enez: Solving problems in a distributed way in membrane computing: dP systems. Int. J. of Computers, Communication and Control, 5, 2 (2010), 238–252. 14. 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. 15. Gh. P˘aun, M.J. P´erez-Jim´enez: P and dP automata: A survey. Lecture Notes in Computer Science, 6570, in press. 16. Gh. P˘aun, M.J. P´erez-Jim´enez: An infinite hierarchy of languages defined by dP systems. Theoretical Computer Sci., in press. 17. Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.: Handbook of Membrane Computing. Oxford University Press, 2010. 18. G. Rozenberg, A. Salomaa, eds.: Handbook of Formal Languages. 3 volumes, Springer, Berlin, 1998. 19. A. Salomaa: Formal Languages. Academic Press, New York, 1973. 20. The P Systems Website: http://ppage.psystems.eu.