Handling Languages with Spiking Neural P Systems with Extended Rules

Handling Languages with Spiking Neural P Systems with Extended Rules Haiming CHEN1, Tseren-Onolt ISHDORJ3, Gheorghe P ˘AUN2,3, Mario J. P´EREZ-JIM´ENEZ3 1Computer Science Laboratory, Institute of Software Chinese Academy of Sciences 100080 Beijing, China E-mail: [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 E-mail: [email protected], [email protected], [email protected] Abstract. We consider spiking neural P systems with spiking rules allowed to introduce zero, one, or more spikes at the same time. A tool-kit for computing (some) operations with languages generated by such systems is provided. Computing the union of languages is easy. However, computing the concatenation or the intersection with a regular language is not so easy. A way to compute weak encoding is also provided. The main results of the computing power of the obtained systems are then presented, when considering them as number generating and as language generating devices. In particular, we find direct characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of restricted rules). 1. Introduction We combine here two ideas recently considered in the study of the spiking neural P systems (in short, SN P systems) introduced in [3], namely the extended rules from [5] and the string generation from [1]. 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. 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. The case of SN P systems as number generators was investigated in several papers, starting with [3], where it is proved that such systems are Turing complete (hence also universal, because the proof is constructive; universality in a rigorous framework was investigated in [5]). In turn, the string case is investigated in [1], where representations of finite, regular, and recursively enumerable languages were obtained, but also finite languages were found which cannot be generated in this way. Here we consider an extension of the rules, already used in [5], namely 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 the next section). Thus, these rules cover and generalize at the same time both spiking rules and forgetting rules as considered so far in this area – with the mentioning that we do not also consider here a delay between firing and spiking, because in the proofs we never need such a delay. In Section 3 we present constructions of SN P systems for computing some usual operations with languages: union, concatenation, weak coding, intersection with regular languages. Computing the union of languages is easy, but computing the concatenation or the intersection with a regular language is not so easy. A way to compute weak encoding is also provided. The main results of the computing power of these systems are recalled in Section 4. As expected, the use of extended rules allows much simpler constructions for the proof of universality in the case of considering SN P systems as number generators. More interesting is the case of strings produced by SN P systems with extended rules: we associate a symbol bito a step when the system sends ispikes into the environment, with two possible cases – b0is used as a separated symbol, or it is replaced by λ(sending no spike outside is interpreted as a step when the generated string is not grown). The first case is again restrictive: not all minimal linear languages can be obtained, but still results stronger than those from [1] can be proved in the new framework because of the possibility of removing spikes under the control of regular expressions. The freedom provided by the existence of steps when we have no output makes possible direct characterizations of finite and recursively enumerable languages (not only representations, modulo various operations with languages, as obtained in [1] for the standard binary case). 2. Spiking Neural P Systems with Extended Rules We assume the reader to be familiar with basic language and automata theory, e.g., from [7] and [8], so that we introduce here only some notations and notions used later in the paper. If x=a1a2. . . an, ai∈V, 1≤i≤n, then mi(x) = an. . . a2a1. A morphism h:V∗ 1−→ V∗ 1such that h(a)∈ {a, λ}for each a∈V1is called a projection, and a morphism h:V∗ 1−→ V∗ 2such that h(a)∈V2∪{λ}for each a∈V1is called a weak coding. 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 the language L2is a singleton, these operations are called left and right derivatives, and denoted by ∂l x(L) = {x}\L and ∂r x(L) = L/{x}, respectively. We denote by FIN, REG, CF, CS, RE the families of finite, regular, context-free, context-sensitive, 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). Let V={b1, b2, . . . , bm}, for some m≥1. For a string x∈V∗, let us denote by valm(x) the value in base m+ 1 of x(we use base m+ 1 in order to consider the symbols b1, . . . , bmas digits 1,2, . . . , m, thus avoiding the digit 0 in the left hand of the string). We extend this notation in the natural way to sets of strings. We directly introduce the type of SN P systems we investigate in this paper; the reader can find details about the standard definition in [3], [6], [1], etc. An extended spiking neural P system (abbreviated as extended SN P system), 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 form E/ac→ap, where Eis a regular expression over aand c≥1, p ≥0, with the restriction c≥p; 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 global clock is assumed, marking the time for the whole system, hence the functioning of the system is synchronized. Note that we do not consider here a delay between firing and spiking (i.e., rules of the form E/ac→ap;d, with d≥0), because we do not need this feature in the proofs below, but such a delay can be introduced in the usual way. (As a consequence, here the neurons are always open.) 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. 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. With any computation (halting or not) we associate a spike train, the sequence of symbols 0 and 1 describing the behavior of the output neuron: if the output neuron spikes, then we write 1, otherwise we write 0 (note that at this stage we ignore the number of spikes emitted by the output neuron into the environment in each step, but this additional information will be considered below). As the result of a computation, in [3] and [6] one considers the distance between two consecutive steps when there are spikes which exit the system, with many possible variants: taking the distance between the first two occurrences of 1 in the spike train, between all consecutive occurrences, considering only alternately the intervals between occurrences of 1, etc. For simplicity, we consider here only the first case mentioned above: we denote by N2(Π) the set of numbers generated by an SN P system in the form of the number of steps between the first two steps of a computation when spikes are emitted into environment, and by Spik2SNePm(rulek, consp, prodq) the family of sets N2(Π) generated by SN P systems with at most mneurons, at most krules in each neuron, consuming at most pand producing at most qspikes. Any of these parameters is replaced by ∗if it is not bounded. Following [1] we can also consider as the result of a computation the spike train itself, thus associating a language with an SN P system. Specifically, like in [1], we can consider the language Lbin(Π) of all binary strings associated with halting computations in Π: the digit 1 is associated with a step when one or more spikes exit the output neuron, and 0 is associated with a step when no spike is emitted by the output neuron. Because several spikes can exit at the same time, we can also work on an arbitrary alphabet: let us associate the symbol biwith a step when the output neuron emits i spikes. We have two cases: interpreting b0(hence a step when no spike is emitted) as a symbol or as the empty string. In the first case we denote the generated language by Lres(Π) (with “res” coming from “restricted”), in the latter one we write Lλ(Π). The respective families are denoted by LαSNePm(rulek, consp, prodq), where α∈ {bin, res, λ}and parameters m, k, p, q are as above. 3. A Tool-Kit for Handling Languages We present first several extended SN P systems which perform operations with languages in order to let the reader have an idea how these systems work. For instance, starting with two SN P systems Π1,Π2, we look for a system Π which generates the language Lλ(Π1)¦Lλ(Π2), where ¦is a binary operation with languages. For the union of languages, such a system Π is easy to be constructed (as already done in [3]): we start with the systems Π1,Π2without any spike inside and we consider a module which non-deterministically activates one of these systems, by introducing in their neurons as many spikes as we have in the initial configurations of Π1and Π2. Not so simple is the case of concatenation, which, however, can be handled as in Fig. 1. We start with system Π1as it is (with the neurons loaded with the necessary spikes), and with system Π2without any spike inside. ¾ ½» ¼ ' & $ % Á¿ À ² ±¯ °² ±¯ ° ² ±¯ ° ' & $ % ' & $ % ² ±¯ ° ' & $ % ' & $ % ² ±¯ °² ±¯ ° ? ¾ ¢ ¢ ¢ ¢ ® AAAAU - ¾ ´´´´´´ ´ 36 - - ½½½½ ½ > 6 ? 6 ©©©©©© © * H H H H H H HY A A A AK P P P P P P P P P P P Pi H H H H H H H HY ©©©©©©©© ©*  Á A A A AK Π1 out ai→ai Π2 d1 am+1+i→a ai→λ 1≤i≤m d2d3 a+/a →aa+/a →a d4 ai→ai am+1+i→am+1+i 1≤i≤m c1cicn ... . . . a→a a →a a →a d5 a3→a a4→λ d6 a2 a2→a2 a2→a d7 a2 a2→a2 Fig. 1. Computing the concatenation of two languages. We have in Fig. 1 three sub-systems/modules with specific tasks to solve. For instance, neurons σd5, σd6, σd7non-deterministically choose a moment when the string generated by system Π1is assumed completed. After using rule a2→ain σd6, neuron σd5fires, this activates neurons σc1, . . . , σcn, and these neurons both “flood” neuron σd4with m+ 1 spikes and activate the neurons of system Π2, introducing as many spikes as Π2has in its initial configuration. Specifically, we have n= max{m+ 1, spin(Π2)}, where mis the cardinality of the alphabet we work with, and spin(Π2) is the maximum of the number of spikes present in any neuron of Π2in the initial configuration. Then we have synapses (ci, d4) for 1 ≤i≤m+ 1, and (ci, k), for σka neuron in Π2, for 1 ≤i≤nk, where nkis the number of spikes present in σkin the initial configuration of Π2. º ¹· ¸º ¹· ¸ º ¹· ¸º ¹· ¸ º ¹· ¸º ¹· ¸ ? ? ? ? ? ? ? ? c1 ai→ai−1 a→a .. . cj ai→ai−1 a→a . . . cm−2 ai→ai−1 a→a c0 1 ai→ai−1 a→a . . . c0 j ai→ai−1 a→a . . . c0 m−2 ai→ai−1 a→a ' & $ % a2k−1→a a2k→λ 1≤k≤m ¶ µ³ ´ ¶ µ³ ´ 6 ? e1 a+/a →a a+/a →a e2 d º ¹· ¸º ¹· ¸ ai→ai i=1, . . . , m ai→ai i= 1, . . . , m c0c0 0 ' & $ % ' & $ % ¾ ½» ¼ - - Π1Π2 out ai→ai 1≤i≤m ?? ? ? s z z - : * 1µ * j Fig. 2. Computing the intersection with a regular language. The pair of neurons σd4, σout takes care of the output of the whole system, first passing the output of Π1to σout and then taking the output of Π2and sending it out. If σd4receives any further spike from Π1after neurons σd5, σd6, σd7have “decided” that the work of Π1is finished, then σd4fires (note that it cannot fire for exactly m+1 spikes), this makes σd1fire, and then the computation will never finish, because of the pair of neurons σd2, σd3. Thus, the computation ends if and only if after sending out a complete string generated by Π1we also send out a string generated by Π2, hence we generate the concatenation of strings produced by the two systems. Consider now an arbitrary SN P system Π1and an SN P system Π2simulating a regular grammar G, with the following changes: chain rules Ai→Aiare added to grammar Gfor all nonterminals Ai; then, we assume that the number of rules (nin the construction) is strictly bigger than the number of symbols (m) – if this is not the case, then we simply duplicate some rules. The system looks now as in Fig. 3 (k can be 0 only for chain rules Ai→Ai, where b0=λ). Thus, after simulating a rule Ai→bk, neurons σ1, σ2are “flooded” and have to stop. The grammar G– and hence also Π2– outputs a terminal symbol after an arbitrary number of steps of using chain rules Ai→Ai, hence steps when nothing exits the system. This makes possible the synchronization of Π1and Π2in the sense that they output spikes in the same steps. What remains to do is to compare the number of spikes emitted by the two systems, so that we can select the strings from the intersection Lλ(Π1)∩Lλ(Π2). ' & $ % ' & $ % ' & $ % ' & $ % - ¾ ? 6 ¶¶¶ ¶ 7 ? - 1 an+m an+m+i→an+m 0≤i≤m 2 an+m an+m+i→an+m 0≤i≤m 3 a2n+m an+m+i/an+m+i−j→ak for Ai→bkAj∈P an+m+i→an+k for Ai→bk∈P 4 ak→ak 1≤k≤m an+k→ak Fig. 3. Simulating a regular grammars having chain rules. This is ensured as suggested in Fig. 2 (in order to keep the figure smaller, we have not indicated the range of parameter i, but it is as follows: in all neurons σcjand σc0 j, 1 ≤j≤m−2, we have 2 ≤i≤m). If the two systems Π1and Π2do not spike at the same time or one sends out r≥1 spikes and the other one s≥1 spikes for r6=s, then the neurons σe1, σe2will get activated and the computation never stops: the spikes emitted by the two systems circulate from top down along the chains of neurons σc0, σc1, . . . , σcm−2and σc0 0, σc0 1, . . . , σc0 m−2, and if we do not obtain exactly one spike at the same time in the two columns, then the neuron σdfires and activates the neurons σe1, σe2. We do not know how to compute – in an elegant way – morphisms, but the particular case of weak codings can be handled as in Fig. 4. The difficulty is to have h(bi)=bjwith i<j, and to this aim the “spike supplier” pair of neurons σc1, σc2is considered. In each step, they send m+1 spikes to neuron σc3. If this neuron receives nothing at the same time from the system Π, then the m+ 1 spikes are forgotten. If ispikes come from system Π, 1 ≤i≤m, then, using the m+ 1 + ispikes, neuron σc3 can send j+ 1 spikes to the output neuron, which emits the right number of spikes to the environment. At any time, the neurons σc1, σc2can stop their work; if this happens prematurely (before having the system Π halted), then neuron σc3will emit only one spike, and this triggers the “never halting module”, composed of the neurons σc4, σc5, σc6, which will continue to work forever. The reader can check that the system produces indeed the language h(Lλ(Π)), for a weak coding hwhich moves some biinto bk, and erases other symbols bj. We do not know how to compute arbitrary morphisms or the other AFL operations, Kleene + and inverse morphisms. ¾ ½» ¼¶ µ³ ´ ² ±¯ ° ' & $ % ' & $ % ' & $ % # "à ! ' & $ % - ? - ¾ - - ?³³³ ³ 1 HHH Hj 6? c1 am+1 am+1 →am+1 am+1 →λ c2 am+1 am+1 →am+1 c3 Π am+1+i→ak+1 for h(bi)=bk am+1+j→λ for h(bj) = λ am+1 →λ ai→a for 1 ≤i≤m out aj→aj−1 2≤j≤m+ 1 c4 a→a ak→λ, k ≥2 c5 a+/a →a c6 a+/a →a Fig. 4. Computing a weak coding. A possible way to address these problems is to reduce them to another problem, that of introducing delays of arbitrarily many steps in between any two steps of computations in an arbitrary SN P system Π (in the same way as the chain rules introduce such “dummy steps” in the work of a regular grammar). If such a slowingdown of a system would be possible, then we can both compute arbitrary morphisms and the intersection of languages generated by two arbitrary SN P systems (not only with one of them generating a regular language, as above). Another open problem of interest (but difficult, we believe) is to find an SN P system, as small as possible in the number of neurons, generating a Dyck language (over at least two pairs of parentheses). If such a systems would be found, then a representation of context-free languages would be obtained, using the Chomsky-Sch¨utzenberger characterization of these languages as the weak coding of the intersection of a Dyck language with a regular language. 4. Computing Power of Extended SN P Systems For the reader convenience, we recall now (without a proof) several results concerning the computing power of SN P systems with extended rules. Details can be found in [2]. 4.1. Extended SN P Systems as Number Generators Because non-extended SN P systems are already computationally universal, this result is directly valid also for extended systems. However, the construction on which the proof is based is much simpler in the extended case (in particular, it does not use the delay feature), that is why we mention it. Theorem 4.1. NRE =Spik2SNeP∗(rule5, cons5, prod2). 4.2. Languages in the Restricted Case We pass now to considering SN P systems as language generators, starting with the restricted case, when the system outputs a symbol in each computation step. In all considerations below, we work with the alphabet V={b1, b2, . . . , bm}, for some m≥1. By a simple renaming of symbols, we may assume that any given language Lis a language over V. When a symbol b0is also used, it is supposed that b0/∈V. 4.2.1. A Characterization of FIN SN P systems with standard rules cannot generate all finite languages (see [1]), but extended rules help in this respect. Lemma 4.1. LαSNeP1(rule∗, cons∗, prod∗)⊆F IN,α∈ {res, λ}. Lemma 4.2. FIN ⊆LαSNeP1(rule∗, cons∗, prod∗), α∈ {res, λ}. Theorem 4.2. FIN =LresSNeP1(rule∗, cons∗, prod∗) = LλSNeP1(rule∗, cons∗, prod∗).