Notes on Spiking Neural P Systems and Finite Automata

Notes on Spiking Neural P Systems and Finite Automata Francis George C. Cabarle1, Henry N. Adorna1, Mario J. P´erez-Jim´enez2 1Department of Computer Science University of the Philippines Diliman Diliman, 1101, Quezon city, Philippines; 2Department of Computer Science and AI Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Spain [email protected], [email protected], [email protected] Summary. Spiking neural P systems (in short, SNP systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SNP systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. SNP transducers were introduced, where both input and output neurons were used. More recently, SNP modules were introduced which generalize SNP transducers: extended rules are used (more than one spike can be emitted each step) and a set of input and output neurons can be used. In this work we continue relating SNP modules and finite automata: (i) we amend previous constructions for DFA and DFST simulations, (ii) improve the construction from three neurons down to one neuron, (iii) DFA with output are simulated, and (iv) we generate automatic sequences using results from (iii). Key words: Membrane computing, Spiking neural P systems, Finite automata, Automatic sequences 1 Introduction Spiking neural P systems (in short, SNP systems) introduced in [7], incorporated into membrane computing the idea of pulse coding of information in computations using spiking neurons (see for example [10][11] and references therein for more information). In pulse coding from neuroscience, pulses known as spikes are not distinct, so information is instead encoded in their multiplicity or the time they are emitted. On the computing side, SNP systems have neurons processing only one object (the spike symbol a), and neurons are placed on nodes of a directed graph. Arcs between neurons are called synapses. SNP systems are known to be universal in 78 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez both generative (an output is given, but not an input) and accepting (an input is given, but not an output) modes. SNP systems can also solve hard problems in feasible (polynomial to constant) time. We do not go into such details, and we refer to [7][8][9][16] and references therein. SNP systems with standard rules (as introduced in their seminal paper) have neurons that can emit at most one pulse (the spike) each step, and either an input or output neuron connected to the environment, but not both. In [15], SNP systems were equipped with both an input and output neuron, and were known as SNP transducers. Furthermore, extended rules were introduced in [3] and [14], so that a neuron can produce more than one spike each step. The introduced SNP modules in [6] can then be seen as generalizations of SNP transducers: more than one spike can enter or leave the system, and more than one neuron can function as input or output neuron. In this work we continue investigations on SNP modules. In particular we amend the problem introduced in the construction of [6], where SNP modules were used to simulate deterministic finite automata and state transducers. Our constructions also reduce the neurons for such SNP modules: from three neurons down to one. Our reduction relies on more involved superscripts, similar to some of the constructions in [12]. We also provide constructions for SNP modules simulating DFA with output. Establishing simulations between DFA with output and SNP modules, we are then able to generate automatic sequences. Such class of sequences contain, for example, a common and useful automatic sequence known as the Thue-Morse sequence. The Thue-Morse sequence, among others, play important roles in many areas of mathematics (e.g. number theory) and computer science (e.g. automata theory). Aside from DFA with output, another way to generate automatic sequences is by iterating morphisms. We invite the interested reader to [1] for further theories and applications related to automatic sequences. This paper is organized as follows: Section 2 provides our preliminaries. Section 3 provides our results. Finally, section 4 provides our final remarks. 2 Preliminaries It is assumed that the readers are familiar with the basics of membrane computing (a good introduction is [13] with recent results and information in the P systems webpage1and a recent handbook [17] ) and formal language theory (available in many monographs). We only briefly mention notions and notations which will be useful throughout the paper. 2.1 Language theory and string notations We denote the set of natural (counting) numbers as N={0,1,2, . . .}. Let Vbe an alphabet, V∗is the set of all finite strings over Vwith respect to concatenation and 1http://ppage.psystems.eu/ Notes on Spiking Neural P Systems and Finite Automata 79 the identity element λ(the empty string). The set of all non-empty strings over V is denoted as V+so V+=V∗− {λ}. We call Va singleton if V={a}and simply write a∗and a+instead of {a}∗and {a}+. If ais a symbol in V, then a0=λ, A regular expression over an alphabet Vis constructed starting from λand the symbols of Vusing the operations union, concatenation, and +. Specifically, (i)λ and each a∈Vare regular expressions, (ii) if E1and E2are regular expressions over Vthen (E1∪E2), E1E2, and E+ 1are regular expressions over V, and (iii) nothing else is a regular expression over V. The length of a string w∈V∗is denoted by |w|. Unnecessary parentheses are omitted when writing regular expressions, and E+∪{λ}is written as E∗. We write the language generated by a regular expression Eas L(E). If Vhas ksymbols, then [w]k=nis the base-krepresentation of n∈N. 2.2 Deterministic finite automata Definition 1. A deterministic finite automaton (in short, a DFA) D, is defined by the 5-tuple D= (Q, Σ, q1, δ, F), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  δ:Q×Σ→Qis the transition function,  q1∈Qis the initial state,  F⊆Qis a set of final states. Definition 2. A deterministic finite state transducer (in short, a DFST) with accepting states T, is defined by the 6-tuple T= (Q, Σ, ∆, q1, δ0, F), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  ∆={c1, . . . , ct}is the output alphabet,  δ0:Q×Σ→Q×∆is the transition function,  q1∈Qis the initial state,  F⊆Qis a set of final states. Definition 3. A deterministic finite automaton with output (in short, a DFAO) M, is defined by the 6-tuple M= (Q, Σ, δ00, q1, ∆, τ), where:  Q={q1, . . . , qn}is a finite set of states,  Σ={b1, . . . , bm}is the input alphabet,  δ00 :Q×Σ→Qis the transition function,  q1∈Qis the initial state,  ∆={c1, . . . , ct}is the output alphabet,  τ:Q→∆is the output function. A given DFAO Mdefines a function from Σ∗to ∆, denoted as fM(w) = τ(δ00(q1, w)) for w∈Σ∗. If Σ={1, ..., k}, denoted as Σk, then Mis a k-DFAO. 80 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez Definition 4. A sequence, denoted as a= (an)n≥0, is k-automatic if there exists ak-DFAO, M, such that given w∈Σ∗ k,an=τ(δ00(q1, w)), where [w]k=n. Example 1. (Thue-Morse sequence) The Thue-Morse sequence t= (tn)n≥0counts the number of 1’s (mod 2) in the base-2 representation of n. The 2-DFAO for t is given in Fig. 1. In order to generate t, the 2-DFAO is in state q1with output 0, if the input bits seen so far sum to 0 (mod 2). In state q2with output 1, the 2-DFAO has so far seen input bits that sum to 1 (mod 2). For example, we have t0= 0, t1=t2= 1, and t3= 0. - - ] ?W 00 1 1 start q1/0q2/1 Fig. 1. 2-DFAO generating the Thue-Morse sequence. 2.3 Spiking neural P systems Definition 5. A spiking neural P system (in short, an SNP system) of degree m≥1, is a construct of the form Π=({a}, σ1, . . . , σm, syn, in, out) where:  {a}is the singleton alphabet (ais called spike);  σ1, . . . , σmare neurons of the form σi= (ni, Ri),1≤i≤m, where: –ni≥0 is the initial number of spikes inside σi; –Riis a finite set of rules of the general form: E/ac→ap;d, where Eis a regular expression over {a},c≥1, with p, d ≥0, and c≥p; if p= 0, then d= 0 and L(E) = {ac};  syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses);  in, out ∈ {1, . . . , m}indicate the input and output neurons, respectively. A rule E/ac→ap;din neuron σi(we also say neuron ior simply σiif there is no confusion) is called a spiking rule if p≥1. If p= 0, then d= 0 and L(E) = {ac}, so that the rule is written simply as ac→λ, known as a forgetting rule. If a spiking rule has L(E) = {ac},we simply write it as ac→ap;d. The systems from the original paper [7], with rules of the form E/ac→a;dand ac→λ, are referred to Notes on Spiking Neural P Systems and Finite Automata 81 as standard systems with standard rules. The extended rules (i.e. p≥1) used in this work are referred to as SNP systems with extended rules in other literature, e.g. [6], [14], [16]. The rules are applied as follows: If σicontains kspikes, ak∈L(E) and k≥c, then the rule E/ac→ap;d∈Riwith p≥1,is enabled and can be applied. Rule application means consuming cspikes, so only k−cspikes remain in σi. The neuron produces pspikes (also referred to as spiking) after dtime units, to every σjwhere (i, j)∈syn. If d= 0 then the pspikes arrive at the same time as rule application. If d≥1 and the time of rule application is t, then during the time sequence t, t + 1, . . . , t +d−1 the neuron is closed. If a neuron is closed, it cannot receive spikes, and all spikes sent to it are lost. Starting at times t+dand t+d+ 1, the neuron becomes open (i.e., can receive spikes), and can apply rules again, respectively. Applying a forgetting rule means producing no spikes. Note that a forgetting rule is never delayed since d= 0. SNP systems operate under a global clock, i.e. they are synchronous. At every step, every neuron that can apply a rule must do so. It is possible that at least two rules E1/ac1→ap1;d1and E2/ac2→ap2;d2, with L(E1)∩L(E2)6=∅, can be applied at the same step. The system nondeterministically chooses exactly one rule to apply. The system is globally parallel (each neuron can apply a rule) but is locally sequential (a neuron can apply at most one rule). Aconfiguration or state of the system at time tcan be described by Ct= hr1/t1, . . . , rm/tmifor 1 ≤i≤m: Neuron icontains ri≥0 spikes and it will open after ti≥0 time steps. The initial configuration of the system is therefore C0= hn1/0, . . . , nm/0i, where all neurons are initially open. Rule application provides us a transition from one configuration to another. A computation is any (finite or infinite) sequence of transitions, starting from a C0. A halting computation is reached when all neurons are open and no rule can be applied. If σout produces ispikes in a step, we associate the symbol bito that step. In particular, the system (using rules in its output neuron) generates strings over Σ={p1, . . . , pm},for every rule r`=E`/aj`→ap`;d`,1≤`≤m, in σout. From [3] we can have two cases: associating b0(when no spikes are produced) with a symbol, or as λ. In this work and as in [6], we only consider the latter. Definition 6. A spiking neural P module (in short, an SNP module) of degree m≥1, is a construct of the form Π=({a}, σ1, . . . , σm, syn, Nin, Nout) where  {a}is the singleton alphabet (ais called spike);  σ1, . . . , σmare neurons of the form σi= (ni, Ri),1≤i≤m, where: –ni≥0 is the initial number of spikes inside σi; –Riis a finite set of rules of the general form: E/ac→ap,where Eis a regular expression over {a},c≥1, and p≥0, with c≥p; if p= 0, then L(E) = {ac}  syn ⊆ {1, . . . , m}×{1, . . . , m}, with (i, i)/∈syn for 1 ≤i≤m(synapses); 82 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez  Nin, Nout(⊆ {1,2, . . . , m}) indicate the sets of input and output neurons, respectively. In [15], SNP transducers operated on strings over a binary alphabet as well considering b0as a symbol. SNP modules, first introduced in [6], are a special type of SNP systems with extended rules, and generalize SNP transducers. SNP modules behave in the usual way as SNP systems, except that spiking and forgetting rules now both contain no delays. In contrast to SNP systems, SNP modules have the following distinguishing feature: at each step, each input neuron σi, i ∈Nin,takes as input multiple copies of afrom the environment (in short, Env); Each output neuron σo, o ∈Nout,produces pspikes to Env, if a rule E/ac→apis applied in σo; Note that Nin ∩Nout is not necessarily empty. 3 Main results In this section we amend and improve constructions given in [6] to simulate DFA and DFST using SNP modules. Then, k-DFAO are also simulated with SNP modules. Lastly, SNP modules are related to k-automatic sequences. 3.1 DFA and DFST simulations We briefly recall the constructions from theorem 8 and 9 of [6] for SNP modules simulating DFAs and DFSTs. The constructions for both DFAs and DFSTs have a similar structure, which is shown in Fig. 2. For neurons 1 and 2 in Fig. 2, the spikes and rules for DFA and DFST simulation are equal, so the constructions only differ for the contents of neuron 3. Let D= (Q, Σ, δ, q1, F) be a DFA, where Σ={b1, . . . , bm},Q={q1, . . . , qn}. The construction for theorem 8 of [6] for an SNP Module ΠDsimulating Dis as follows: ΠD= ({a}, σ1, σ2, σ3, syn, {3},{3}), where  σ1=σ2= (n, {an→an}),  σ3= (n, {a2n+i+k/a2n+i+k−j→aj|δ(qi, bk) = qj}),  syn ={(1,2),(2,1),(1,3)}. The structure for ΠDis shown in Fig. 2. Note that n, m ∈N,are fixed numbers, and each state qi∈Qis represented as aispikes in σ3, for 1 ≤i≤n. For each symbol bk∈Σ, the representation is an+k. The operation of ΠDis as follows: σ1 and σ2interchange anspikes at every step, while σ1also sends anspikes to σ3. Suppose that Dis in state qiand will receive input bk, so that σ3of ΠDhas ai spikes and will receive an+kspikes. In the next step, σ3will collect anspikes from σ1,an+kspikes from Env, so that the total spikes in σ3is a2n+i+k. A rule in σ3 with L(E) = {a2n+i+k}is applied, and the rule consumes 2n+i+k−jspikes, Notes on Spiking Neural P Systems and Finite Automata 83 therefore leaving only ajspikes. A single state transition δ(qi, bk) = qjis therefore simulated. With a 1-step delay, ΠDreceives a given input w=bi1, . . . , birin Σ∗and produces a sequence of states z=qi1, . . . , qir(represented by ai1, . . . , air) such that δ(qi`, bi`) = qi`+1 ,for each `= 1, . . . , r where qi1=q1. Then, wis accepted by D(i.e. δ(q1, w)∈F) iff z= ΠD(w) ends with a state in F(i.e. qir∈F). Let the language accepted by ΠDbe defined as: L(ΠD) = {w∈Σ∗|ΠD(w)∈Q∗F}. Then, the following is theorem 8 from [6] Theorem 1. (Ibarra et al [6]) Any regular language Lcan be expressed as L= L(ΠD)for some SNP module ΠD. ' & $ % ' & $ %  - ? 12 ' & $ %  3 Fig. 2. Structure of SNP modules from [6] simulating DFAs and DFSTs. The simulation of DFSTs requires a slight modification of the DFA construction. Let T= (Q, Σ, ∆, δ0, q1, F) be a DFST, where Σ={b1, . . . , bk}, ∆={c1, . . . , ct},Q={q1, . . . , qn}. We construct the following SNP module simulating T: ΠT= ({a}, σ1, σ2, σ3, syn, {3},{3}), where:  σ1=σ2= (n, {an→an}),  σ3= (n, {a2n+i+k+t/a2n+i+k+t−j→an+s|δ0(qi, bk)=(qj, cs)}),  syn ={(1,2),(2,1),(1,3)}. The structure for ΠTis shown in Fig. 2. Note that n, m, t ∈Nare fixed numbers. For 1 ≤i≤n, 1≤s≤t, 1≤k≤m: each state qi∈Q, each input symbol bk∈Σ, and each output symbol cs∈∆, is represented by ai,an+t+k, and an+s, respectively. The operation of ΠTgiven an input w∈Σ∗is in parallel to the operation of ΠD; the difference is that the former produces a cs∈∆, while the latter produces 84 F.G.C. Cabarle, H.N. Adorna, M.J. P´erez-Jim´enez aqi∈Q. From the construction of ΠTand the claim in Theorem 1, the following is Theorem 9 from [6]: Theorem 2. (Ibarra et al[6]) Any finite transducer Tcan be simulated by some SNP module ΠT. The previous constructions from [6] on simulating DFAs and DFSTs have however, the following technical problem: Suppose we are to simulate DFA Dwith at least two transitions, (1) δ(qi, bk) = qj,and (2) δ(qi0, bk0) = qj0. Let j6=j0, i =k0,and k=i0. The SNP module ΠD simulating Dthen has at least two rules in σ3:r1=a2n+i+k/a2n+i+k−j→aj, (simulating (1)) and r2=a2n+i0+k0/a2n+i0+k0−j0→aj0(simulating (2)). Observe that 2n+i+k= 2n+i0+k0,so that in σ3, the regular expression for r1is exactly the regular expression for r2. We therefore have a nondeterministic rule selection in σ3. However, Dbeing a DFA, transitions to two different states qjand qj0. Therefore, ΠDis a nondeterministic SNP module that can, at certain steps, incorrectly simulate the DFA D. This nondeterminism also occurs in the DFST simulation. An illustration of the problem is given in example 2. Example 2. We modify the 2-DFAO in Fig. 1 into a DFA in Fig. 3 as follows: Instead of Σ={0,1}, we have Σ={1,2}; We maintain n=m= 2, however, the transitions are swapped, so in Fig. 3 we have the following two (among four) transitions: δ(q1,2) = q2,and δ(q2,1) = q1. These two transitions cause the nondeterministic problem for the SNP module given in Fig. 4. The problem concerns the simulation of the two previous transitions using rules a7/a5→a2and a7/a6→a in σ3, which can be nondeterministically applied: if σ3contains a2spikes and receives a3from Env (representing input 1 for the DFA), at the next step σ3will have a7spikes, allowing the possibility of an incorrect simulation. - - ] ?W 12 2 1 start q1q2 Fig. 3. DFA with incorrect simulation by the SNP module in Fig. 4. Next, we amend the problem and modify the constructions for simulating DFAs and DFSTs in SNP modules. Given a DFA D, we construct an SNP module Π0 D simulating Das follows: Notes on Spiking Neural P Systems and Finite Automata 85 # " ! # " !  - ? 1 a2 a2→a2 2 a2 a2→a2 ' & $ %  3 a2 a6/a5→a a7/a5→a2 a7/a6→a a8/a7→a2 Fig. 4. SNP module with incorrect simulation of the DFA in Fig. 3. Π0 D= ({a}, σ1, syn, {1},{1}), where  σ1= (1,{ak(2n+1)+i/ak(2n+1)+i−j→aj|δ(qi, bk) = qj}),  syn =∅. We have ΠDcontaining only 1 neuron, which is both the input and output neuron. Again, n, m ∈Nare fixed numbers. Each state qiis again represented as aispikes, for 1 ≤i≤n. Each symbol bk∈Σis now represented as ak(2n+1) spikes. The operation of Π0 Dis as follows: neuron 1 starts with a1spike, representing q1in D. Suppose that Dis in some state qi, receives input bk, and transitions to qjin the next step. We then have Π0 Dcombining ak(2n+1) spikes from Env with aispikes, so that a rule with regular expression ak(2n+1)+iis applied, producing ajspikes to Env. After applying such rule, ajspikes remain in σ1,and a single transition of D is simulated. Note that the construction for Π0 Ddoes not involve nondeterminism, and hence the previous technical problem: Let Dhave at least two transitions, (1) δ(qi, bk) = qj,and (2) δ(qi0, bk0) = qj0. We again let j6=j0, i =k0,and k=i0. Note that being a DFA, we have i6=k. Observe that k(2n+ 1) + i6=k0(2n+ 1) + i0.Therefore, Π0 Dis deterministic, and has two rules r1and r2correctly simulating (1) and (2), respectively. We now have the following result. Theorem 3. Any regular language Lcan be expressed as L=L(Π0 D)for some 1-neuron SNP module Π0 D For a given DFST T, we construct an SNP module Π0 Tsimulating Tas follows: Π0 T= ({a}, σ1, syn, {1},{1}), where  σ1= (1,{ak(2n+1)+i+t/ak(2n+1)+i+t−j→an+s|δ0(qi, bk)=(qj, cs)}),  syn =∅.