Notes on spiking neural P systems and finite automata

Notes on spiking neural P systems and finite automata Francis George C. Cabarle 1 •Henry N. Adorna 1 • Mario J. Pe ´rez-Jime ´nez 2 Published online: 6 July 2016 ÓSpringer Science+Business Media Dordrecht 2016 Abstract Spiking neural P systems (in short, SN P systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SN P 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. A variant known as SN P modules generalize SN P systems by using extended rules (more than one spike can be emitted each step) and a set of input and output neurons. In this work we continue relating SN P modules and finite automata. In particular, we amend and improve previous constructions for the simulatons of deterministic finite automata and state transducers. Our improvements reduce the number of neurons from three down to one, so our results are optimal. We also simulate finite automata with output, and we use these simulations to generate automatic sequences. Keywords Membrane computing Spiking neural P systems Finite automata Automatic sequence 1 Introduction Spiking neural P systems (in short, SN P systems) introduced in Ionescu et al. (2006), incorporated into membrane computing the idea of pulse coding of information in computations using spiking neurons [see for example Maass 2002; Maass and Bishop 1999 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, SN P 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. SN P systems are known to be universal in both generative (an output is given, but not an input) and accepting (an input is given, but not an output) modes. SN P systems can also solve hard problems in feasible (polynomial to constant) time. Another active line of investigation on the computability and complexity of SN P systems is taking mathematical and biological inspirations in order to create new variants, e.g. asynchronous operation, weighted synapses, rules on synapses, structural plasticity. We do not go into details, and we refer to Cabarle et al. (2015), Ionescu et al. (2006), Leporati et al. (2007), Pan et al. (2011), Pa ˘un and Pe ´rez-Jime ´nez (2009), Song and Pan (2015), Song et al. (2015), Zeng et al. (2014), Zeng et al. (2013) and Zhang et al. (2015) and references therein. SN P 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 Pa ˘un et al. (2007), SN P systems were equipped with both an input and output neuron, and were known as SN P transducers. Furthermore, extended rules were introduced in Chen et al. (2008) and Pa ˘un and Pa ˘un (2007), so that a &Francis George C. Cabarle [email protected] Henry N. Adorna [email protected] Mario J. Pe ´rez-Jime ´nez [email protected] 1 Algorithms and Complexity Lab, Department of Computer Science, University of the Philippines Diliman, Diliman, Quezon City 1101, Philippines 2 Department of Computer Science and AI, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Seville, Spain 123 Nat Comput (2016) 15:533–539 DOI 10.1007/s11047-016-9563-4 neuron can produce more than one spike each step. The introduced SN P modules in Ibarra et al. (2010) can then be seen as generalizations of SN P 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 SN P modules. In particular we amend the problem introduced in the construction of Ibarra et al. (2010), where SN P modules were used to simulate deterministic finite automata and state transducers. Our constructions also reduce the neurons for such SN P modules: from three neurons down to one. Our reduction relies on more involved superscripts, similar to some of the constructions in Neary (2010). We also provide constructions for SN P modules simulating DFA with output. Establishing simulations between DFA with output and SN P modules, we are then able to generate automatic sequences. Such class of sequences contain, for example, a well known 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 Allouche and Shallit (2003) for further theories and applications related to automatic sequences. This paper is organized as follows: Sect. 2provides our preliminaries. In Sect. 3the main results are presented. Lastly, some final remarks are drawn and then provided in Sect. 4. 2 Preliminaries It is assumed that the readers are familiar with the basics of membrane computing (a good introduction is Pa ˘un (2002) with recent results and information in the P systems webpage in http://ppage.psystems.eu/ and a recent handbook in Pa ˘un et al. (2010) ) 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 numbers as N¼f0;1;2;...g. Let Vbe an alphabet, Vis the set of all finite strings over V with respect to concatenation and the identity element k(the empty string). The set of all non-empty strings over Vis denoted as Vþso Vþ¼Vfkg. We call Va singleton if V¼fagand simply write aand aþinstead of fagand fagþ.Ifais a symbol in V, then a0¼k, A regular expression over an alphabet Vis constructed starting from kand the symbols of Vusing the operations union, concatenation, and þ. Specifically, (i) kand each a2Vare 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 w2Vis denoted by |w|. Unnecessary parentheses are omitted when writing regular expressions, and Eþ[fkg is written as E. We write the language associated with a regular expression Eas L(E). If Vhas ksymbols, then ½wk¼ nis the base-krepresentation of n2N. 2.2 Deterministic finite automata Definition 1 Adeterministic finite automaton (in short, a DFA) D, is a 5-tuple D¼ðQ;R;q1;d;FÞ, where: –Q¼fq1;...;qngis a finite set of states, –R¼fb1;...;bmgis the input alphabet, –d:QR!Qis the transition function, –q12Qis the initial state, –FQis a set of final states. Definition 2 Adeterministic finite state transducer (in short, a DFST) with accepting states T, is a 6-tuple T¼ðQ;R;D;q1;d0;FÞ, where Q,R,q1, and Fare as above, and D¼fc1;...;ctgis the output alphabet, while d0:QR!QDis the transition function. Definition 3 Adeterministic finite automaton with output (in short, a DFAO) M, is a 6-tuple M¼ðQ;R;d;q1;D;sÞ, where Q;d;R;q1, and Dare as above, and s:Q!Dis the output function. A given DFAO Mdefines a function from Rto D, denoted as fMðwÞ¼sðdðq1;wÞÞ for w2R.If R¼f1; :::; kg, denoted as Rk, then Mis a k-DFAO. Definition 4 A sequence a¼ðanÞn0,isk-automatic if there exists a k-DFAO, M, such that given w2R k, an¼fMðwÞ¼sðdð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 tis given in Fig. 1. In order to generate t, the 2-DFAO is in state q1 with 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. 2.3 Spiking neural P systems Definition 5 Aspiking neural P system (in short, an SN P system) of degree m1, is a tuple of the form P¼ðfag;r1;...;rm;syn;in;outÞ 534 F. G. C. Cabarle et al. 123 where: –fagis the singleton alphabet (ais called spike); –r1;...;rmare neurons of the form ri¼ ðni;RiÞ;1im;where: –ni0 is the initial number of spikes inside ri; –Riis a finite set of rules of the general form: E=ac!ap, where Eis a regular expression over fag,c1, with p0, and cp; –syn f1;...;mgf1;...;mg, with ði;iÞ 62 syn for 1im(synapses); –in;out 2f1;...;mgindicate the input and output neurons, respectively. A rule E=ac!ap;din neuron ri(we also say neuron i or simply riif there is no confusion) is called a spiking rule if p1. If p¼0, the rule is written simply as ac!k, known as a forgetting rule. If a spiking rule has LðEÞ¼ facg;we simply write it as ac!ap. The rules are applied as follows: If ricontains kspikes, ak2LðEÞand kc, then the rule E=ac!ap2Riwith p1;is enabled and can be applied. Rule application means consuming cspikes, so only kcspikes remain in ri. The neuron produces pspikes (also referred to as spiking) to every rjwhere ði;jÞ2syn. Applying a forgetting rule means producing no spikes. SN P 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!ap1and E2=ac2!ap2, 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;...;rmifor 1 im, where neuron icontains ri0 spikes. The initial configuration of the system is therefore C0¼hn1;...;nmi. Rule application provides us a transition from one configuration to another. A computation is any (finite or infinite) sequence of configurations such that: (a) the first term is the initial configuration C0; (b) for each n2, the nth configuration of the sequence is obtained from the previous configuration in one transition step; and (c) if the sequence is finite (called halting computation) then the last term is a halting configuration, i.e. a configuration where all neurons are open and no rule can be applied. If rout 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 R¼ fp1;...;pmg;for every rule r‘¼E‘=aj‘!ap‘;1‘m; in rout. From Chen et al. (2008) we can have two cases: associating b0(when no spikes are produced) with a symbol, or as k. In this work and as in Ibarra et al. (2010), we only consider the latter. Definition 6 Aspiking neural P module (in short, an SN P module) of degree m1, is a tuple of the form P¼ ðfag;r1;...;rm;syn;Nin;NoutÞwhere fag;r1;...;rm;syn are as above and Nin;Nout f1;2;...;mgindicate the sets of input and output neurons, respectively. SN P transducers in Pa ˘un et al. (2007) operated on strings over a binary alphabet as well considering b0as a symbol. SN P modules in Ibarra et al. (2010) are a special type of SN P systems with extended rules and they generalize SN P transducers. SN P modules behave in the usual way as SN P systems, except that spiking and forgetting rules now both contain no delays. In contrast to SN P systems, SN P modules have the following distinguishing feature: at each step, each input neuron ri;i2Nin;takes as input multiple copies of afrom the environment; Each output neuron ro;o2Nout;produces pspikes to the enviroment, if a rule E=ac!apis applied in ro; Note that Nin \Nout is not necessarily empty. 3 Main results In this section we amend and improve constructions given in Ibarra et al. (2010) to simulate DFA and DFST using SN P modules. Then, k-DFAO are also simulated with SN P modules. Lastly, SN P modules are related to k-automatic sequences. 3.1 DFA and DFST simulations We briefly recall the constructions from Theorems 8 and 9 of Ibarra et al. (2010) for SN P modules simulating DFAs and DFSTs. The constructions for both DFAs and DFSTs have a similar structure, which is shown in Fig. 2. Let D¼ðQ;R;d;q1;FÞbe a DFA, where R¼fb1;...;bmg, Q¼fq1;...;qng. The construction for Theorem 8 of Ibarra et al. (2010) for an SN P Module PDsimulating Dis as follows: PD¼ðfag;r1;r2;r3;syn;f3g;f3gÞ; q1/0 start q2/1 0 1 1 0 Fig. 1 2-DFAO generating the Thue-Morse sequence Notes on spiking neural P systems and finite automata 535 123 where –r1¼r2¼ðn;fan!angÞ; –r3¼ðn;fa2nþiþk=a2nþiþkj!ajjdðqi;bkÞ¼qjgÞ; –syn ¼fð1;2Þ;ð2;1Þ;ð1;3Þg: The structure for PDis shown in Fig. 2. Note that n;m2 N;are fixed numbers, and each state qi2Qis represented as aispikes in r3, for 1 in. For each symbol bk2R, the representation is anþk. The operation of PDis as follows: r1and r2interchange anspikes at every step, while r1also sends anspikes to r3. Suppose that Dis in state qiand will receive input bk,so that r3of PDhas aispikes and will receive anþkspikes. In the next step, r3will collect anspikes from r1,anþkspikes from the enviroment, so that the total spikes in r3is a2nþiþk. A rule in r3with LðEÞ¼fa2nþiþkgis applied, and the rule consumes 2nþiþkjspikes, therefore leaving only ajspikes. A single state transition dðqi;bkÞ¼qjis therefore simulated. With a 1-step delay, PDreceives a given input w¼ bi1;...;birin Rand produces a sequence of states z¼ qi1;...;qir(represented by ai1;...;air) such that dðqi‘;bi‘Þ¼qi‘þ1;for each ‘¼1;...;rwhere qi1¼q1. Then, wis accepted by D(i.e. dðq1;wÞ2F) iff z¼PDðwÞ ends with a state in F(i.e. qir2F). Let the language accepted by PDbe defined as: LðPDÞ¼fw2RjPDðwÞ2QFg: Then, the following is Theorem 8 from Ibarra et al. (2010) Theorem 1 (Ibarra et al. 2010)Any regular language L can be expressed as L ¼LðPDÞfor some SN P module PD. The simulation of DFSTs requires a slight modification of the DFA construction. Let T¼ðQ;R;D;d0;q1;FÞbe a DFST, where R¼fb1;...;bkg;D¼fc1;...;ctg;Q¼ fq1;...;qng. We construct the following SN P module simulating T: PT¼ðfag;r1;r2;r3;syn;f3g;f3gÞ; where: –r1¼r2¼ðn;fan!angÞ; –r3¼ðn;fa2nþiþkþt=a2nþiþkþtj!anþsjd0ðqi;bkÞ¼ ðqj;csÞgÞ; –syn ¼fð1;2Þ;ð2;1Þ;ð1;3Þg: The structure for PTis shown in Fig. 2. Note that n;m;t2Nare fixed numbers. For 1 in; 1km;1st: each state qi2Q, each input symbol bk2R, and each output symbol cs2D, is represented by ai,anþtþk, and anþs, respectively. The operation of PTgiven an input w2Ris in parallel to the operation of PD; the difference is that the former produces a cs2D, while the latter produces a qi2Q. From the construction of PTand the claim in Theorem 1, the following is Theorem 9 from Ibarra et al. (2010): Theorem 2 (Ibarra et al. 2010)Any finite transducer T can be simulated by some SN P module PT. The previous constructions from Ibarra et al. (2010)on simulating DFAs and DFSTs have however, the following technical problem: Suppose we are to simulate DFA Dwith at least two transitions, (1) dðqi;bkÞ¼qj;and (2) dðqi0;bk0Þ¼qj0. Let j6¼ j0;i¼k0;and k¼i0. The SN P module PDsimulating Dthen has at least two rules in r3: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 r3, the regular expression for r1is exactly the regular expression for r2. We therefore have a nondeterministic rule selection in r3. However, Dbeing a DFA, transitions to two different states qjand qj0should be deterministic. Therefore, PDis a nondeterministic SN P module that can, at certain steps, incorrectly simulate the DFA D. This nondeterminism also occurs in the DFST simulation. Next, we amend the problem and modify the constructions for simulating DFAs and DFSTs in SN P modules. Given a DFA D, we construct an SN P module P0 Dsimulating Das follows: P0 D¼ðfag;r1;syn;f1g;f1gÞ; where –r1¼ð1;fakðnþ1Þþi=akðnþ1Þþij!ajjdðqi;bkÞ¼qjgÞ; –syn ¼;: We have PDcontaining only 1 neuron, which is both the input and output neuron. Again, n;m2Nare fixed numbers. Each state qiis again represented as aispikes, for 1in. Each symbol bk2Ris now represented as akðnþ1Þ 12 1 2 3 Fig. 2 Structure of SN P modules from Ibarra et al. (2010) simulating DFAs and DFSTs 536 F. G. C. Cabarle et al. 123 spikes. The operation of P0 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 P0 Dcombining akðnþ1Þspikes from the enviroment with aispikes, so that a rule with regular expression akðnþ1Þþiis applied, producing ajspikes to the enviroment. After applying such rule, ajspikes remain in r1;and a single transition of Dis simulated. Note that the construction for P0 Ddoes not involve nondeterminism, and hence the previous technical problem: Let Dhave at least two transitions, (1) dðqi;bkÞ¼qj; and (2) dð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ðnþ1Þþi6¼ k0ðnþ1Þþi0:Therefore, P0 Dis deterministic, and has two rules r1and r2correctly simulating (1) and (2), respectively. We now have the following result. Theorem 3 Any regular language L can be expressed as L¼LðP0 DÞfor some 1-neuron SN P module P0 D For a given DFST T, we construct an SN P module P0 T simulating T as follows: P0 T¼ðfag;r1;syn;f1g;f1gÞ; where –r1¼ð1;fakðnþ1Þþiþt=akðnþ1Þþiþtj!anþsjd0ðqi;bkÞ¼ ðqj;csÞgÞ; –syn ¼;. We also have P0 Tas a 1-neuron SN P module similar to P0 D. Again, n;m;t2Nare fixed numbers, and for each 1in;1km;and 1 st: each state qi2Q, each input symbol bk2R, and each output symbol cs2D,is represented as ai;akðnþ1Þþt;and anþsspikes, respectively. The functioning of P0 Tis in parallel to P0 D. Unlike PT,P0 T is deterministic and correctly simulates T. We now have the next result. Theorem 4 Any finite transducer T can be simulated by some 1-neuron SN P module P0 T. 3.2 k-DFAO simulation and generating automatic sequences Next, we modify the construction from Theorem 4 specifically for k-DFAOs by: (a) adding a second neuron r2 to handle the spikes from r1until end of input is reached, and (b) using r2to output a symbol once the end of input is reached. Also note that in k-DFAOs we have tn, since each state must have exactly one output symbol associated with it. Observing k-DFAOs from Definition 3and DFSTs from Definition 2, we find a subtle but interesting distinction as follows: The output of the state after reading the last symbol in the input is the requirement from a k-DFAO, i.e. for every wover some Rk, the k-DFAO produces only one c2D (recall the output function s); In contrast, the output of DFSTs is a sequence of QD(states and symbols), since dðqi;bkÞ¼ðqj;csÞ. Therefore, if we use the construction in Theorem 4for DFST in order to simulate k-DFAOs, we must ignore the first jwj1 symbols in the output of the system in order to obtain the single symbol we require. For a given k-DFAO M¼ðQ;R;D;d;q1;sÞ, we have 1i;jn,1st, and 1 km. Construction of an SN P module PMsimulating M, is as follows: P¼ðfag;r1;r2;syn;f1g;f2gÞ; where –r1¼ð1;R1Þ;r2¼ð0;R2Þ; –R1¼fakðnþ1Þþiþt=akðnþ1Þþiþtj!anþsjdðqi;bkÞ¼ qj;sðqjÞ¼csg [famðnþ1Þþnþtþi!amðnþ1Þþnþtþij1ing; –R2¼fanþs!kjsðqiÞ¼csg[famðnþ1Þþnþtþi! anþsjsðqiÞ¼csg; –syn ¼fð1;2Þg: We have PMas a 2-neuron SN P module, and n;m;t2Nare fixed numbers. Each state qi2Q, each input symbol bk2R; and each output symbol cs2D, is represented as ai,akðnþ1Þþt, and anþsspikes, respectively. In this case however, we add an end-of-input symbol $ (represented as amðnþ1Þþnþtspikes) to the input string, i.e. if w2R, the input for PMis w$. For any bk2R,r1of PMfunctions in parallel to r1of P0 D and P0 T, i.e. every transition dðqi;bkÞ¼qjis correctly simulated by r1. The difference however lies during the step when $ enters r1, indicating the end of the input. Suppose during this step r1has aispikes, then those spikes are combined with the amðnþ1Þþnþtspikes from the enviroment. Then, one of the nrules in r1with regular expression amðnþ1Þþnþtþi is applied, sending amðnþ1Þþnþtþispikes to r2. The first function of r2is to erase, using forgetting rules, all anþsspikes it receives from r1. Once r2receives amðnþ1Þþnþtþispikes from r1, this means that the end of the input has been reached. The second function of r2is to produce anþsspikes exactly once, by using one rule of the form amðnþ1Þþnþtþi!anþs:The output function sðdðq1;w$ÞÞ is therefore correctly simulated. We can then have the following result. Theorem 5 Any k-DFAO M can be simulated by some 2- neuron SN P module PM. Notes on spiking neural P systems and finite automata 537 123 Next, we establish the relationship of SN P modules and automatic sequences. Theorem 6 Let a sequence a¼ðanÞn0be k-automatic, then it can be generated by some 2-neuron SN P module P. k-automatic sequences have several interesting robustness properties. One property is the capability to produce the same output sequence given that the input string is read in reverse, i.e. for some finite string w¼a1a2...an,we have wR¼anan1...a2a1. It is known [e.g. Allouche and Shallit (2003)] that if ðanÞn0is a k-automatic sequence, then there exists a k-DFAO Msuch that an¼sðdðq0;wRÞÞ for all n0, and all w2R k;where ½wk¼n. Since the construction of Theorem 5simulates both dand s, we can include robustness properties as the following result shows. Theorem 7 Let a¼ðanÞn0be a k-automatic sequence. Then, there is some 2-neuron SN P module Pwhere PðwR$Þ¼an;w2R k;½wk¼n;and n0. 4 Final remarks We have shown that a single neuron in an SN P module is enough to simulate a DFA or DFST, and this is the optimal result in terms of the number of neurons per module (improving and amending some constructions in Ibarra et al. (2010)). In this simulating SN P module with one neuron, a rule simulates a transition in the simulated finite automata, i.e. given a simulated DFA or DFST with mnumber of transitions, the simulating SN P module with neuron ihas jRij¼m. The SN P module simulating a k-DFAO contains two neurons: the general idea is that the first neuron simulates dwhile the second neuron simulates sof the simulated k- DFAO. We were then able to generate automatic sequences using SN P modules, as well as transfer some robustness properties of k-DFAOs to the simulating module. In Chen et al. (2008), strict inclusions for the types of languages characterized by SN P systems with extended rules having one, two, and three neurons were given. Then in Pa ˘un et al. (2007), it was shown that there isno SN P transducerthat can compute nonerasing and nonlength preserving morphisms: for all a2R, the former is a morphism hsuch that hðaÞ 6¼ k, while the latter is a morphism hwhere jhðaÞj  2. It is known [e.g. in Allouche and Shallit (2003)] that the Thue- Morse morphism is given by lð0Þ¼01 and lð1Þ¼10. It is interesting to further investigate SN P modules with respect to other classes of sequences, morphisms, and finite transition systems. Another technical note is that in Pa ˘un et al. (2007)a time step without a spike entering or leaving the system was considered as a symbol of the alphabet, while in Ibarra et al. (2010) (and in this work) it was considered as k. We also leave as an open problem a more systematic analysis of input/output encoding size and system complexity: in the constructions for Theorems 3–4,SNP modules consist of only one neuron for each module, compared to three neurons in the constructions of Ibarra et al. (2010). However, the encoding used in our results is more involved, i.e. with multiplication and addition of indices (instead of simply addition of indices in Ibarra et al. (2010)). On the practical side, SN P modules might also be used for computing functions, as well as other tasks involving (streams of) input-output transformations. Practical applications might include image modification or recognition, sequence analyses, online algorithms, et al. For example, perhaps improving or extending the work done in Dı ´az-Pernil et al. (2013). Some preliminary work on SN P modules and morphisms was given in Cabarle et al. (2012). From finite sequences, it is interesting to extend SN P modules to infinite sequences. In Freund and Oswald (2008), extended SN P systems 1 were used as acceptors of x-languages. SN P modules could also be a way to ‘‘go beyond Turing’’ by way of interactive computations, as in interactive components or transducers given in Goldin et al. (2006). While the syntax of SN P modules may prove sufficient for these ‘‘interactive tasks’’, or at least requiring only minor modifications, a (major) change in the semantics is probably necessary. Acknowledgments Cabarle is supported by a scholarship from the DOST-ERDT of the Philippines. Adorna is funded by a DOST-ERDT grant, the Semirara Mining Corp. professorial chair of the College of Engineering, UP Diliman, and the UP Diliman Gawad Tsanselor 2015 grant. M.J. Pe ´rez-Jime ´nez acknowledges the support of the Project TIN2012-37434 of the ‘‘Ministerio de Economı ´a y Competitividad’’ of Spain, co-financed by FEDER funds. Fruitful discussions with Miguel A ´ngel Martı ´nez-del Amor are also acknowledged. References Allouche J-P, Shallit J (2003) Automatic sequences: theory, applications. Cambridge University Press, Cambridge Cabarle FGC, Bun ˜o KC, Adorna HN (2012) Spiking neural P systems generating the Thue-Morse sequence. In: Asian conference on membrane computing (2012) pre-proceedings, pp 15–18 Oct. Wuhan, China Cabarle FGC, Adorna HN, Pe ´rez-Jime ´nez MJ, Song T (2015) Spiking neural P systems with structural plasticity. Neural Comput Appl 26(8):1905–1917 Chen H, Ionescu M, Ishdorj T-O, Pa ˘un A, Pa ˘un G, Pe ´rez-Jime ´nez MJ (2008) Spiking neural P systems with extended rules: universality and languages. Natural Comput 7:147–166 1 or ESN P systems, in short, are generalizations of SN P systems almost to the point of becoming tissue P systems. ESN P systems are thus generalizations also of (and not to be confused with) SN P systems with extended rules. 538 F. G. C. Cabarle et al. 123 Dı ´az-Pernil D, Pen ˜a-Cantillana F, Gutie ´rrez-Naranjo MA (2013) A parallel algorithm for skeletonizing images by using spiking neural P systems. Neurocomputing 115:81–91 Freund R, Oswald M (2008) Regular x-languages defined by finite extended spiking neural P systems. Fundam Inform 81(1–2): 65–73 Goldin D, Smolka S, Wegner P (eds) (2006) Interactive computation: the new paradigm. Springer, Berlin Ibarra O, Pere ´z-Jime ´nez MJ, Yokomori T (2010) On spiking neural P systems. Nat Comput 9:475–491 Ionescu M, Pa ˘un G, Yokomori T (2006) Spiking neural P systems. Fundam Inform 71(2,3):279–308 Leporati A, Zandron C, Ferretti C, Mauri G (2007) Solving numerical NP-complete problems with spiking neural P systems. In: Eleftherakis G, Kefalas P, Pa ˘un G, Rozenberg G, Salomaa A (eds) Membrane computing: 8th international workshop, WMC 2007 Thessaloniki, Greece, June 25-28, 2007 revised selected and invited papers, Springer, Berlin/Heidelberg, pp 336–352. doi:10.1007/978-3-540-77312-2_21 Maass W (2002) Computing with spikes. Found Inform Process TELEMATIK 8(1):32–36 Maass W, Bishop C (eds) (1999) Pulsed neural networks. MIT Press, Cambridge Neary T (2010) A boundary between universality and non-universal- ity in extended spiking neural P systems. In: Martin-Vide C, Fernau H, Dediu AH (eds) Language and automata theory and applications: 4th international conference, LATA 2010, Trier, Germany, May 24-28, 2010, Proceedings. Springer, Berlin/ Heidelberg, pp 475–487. doi:10.1007/978-3-642-13089-2_40 Pan L, Pa ˘un G, Pe ´rez-Jime ´nez MJ (2011) Spiking neural P systems with neuron division and budding. Sci China Inform Sci 54(8):1596–1607 Pa ˘un G (2002) Membrane computing: an introduction. Springer, Berlin Pa ˘un A, Pa ˘un G (2007) Small universal spiking neural P systems. BioSystems 90(1):48–60 Pa ˘un G, Pe ´rez-Jime ´nez MJ, Rozenberg G (2007) Computing morphisms by spiking neural P systems. J Found Comput Sci 8(6):1371–1382 Pa ˘un G, Pe ´rez-Jime ´nez MJ (2009) Spiking neural P systems. Recent results, research topics. In: Condon A et al (eds) Algorithmic bioprocesses. Springer, Berlin Pa ˘un G, Rozenberg G, Salomaa A (eds) (2010) The Oxford handbook of membrane computing. OUP, Oxford Song T, Pan L (2015) Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy. IEEE Trans NanoBiosci 14(1):38–44 Song T, Zou Q, Liu X, Zeng X (2015) Asynchronous spiking neural P systems with rules on synapses. NeuroComputing 152(2015): 1439–1445 The P systems webpage http://ppage.psystems.eu/ Zeng X, Pan L, Pe ´rez-Jime ´nez MJ (2013) Small universal simple spiking neural P systems with weights. Sci China Inform Sci 57(9):1–11 Zeng X, Zhang X, Song T, Pan L (2014) Spiking neural P systems with thresholds. Neural Comput 26(7):1340–1361 Zhang X, Pan L, Pa ˘un A (2015) On the universality of axon P systems. IEEE Trans Neural Netw Learn Syst 26(11):2816–2829 Notes on spiking neural P systems and finite automata 539 123