Matrix Representation of Spiking Neural P Systems

Matrix Representation of Spiking Neural P Systems Xiangxiang Zeng1,HenryAdorna2,MiguelA´ ngel Mart´ınez-del-Amor3, Linqiang Pan1,and MarioJ.P´erez-Jim´enez3 1Image Processing and Intelligent Control Key Laboratory of Education Ministry Department of Control Science and Engineering Huazhong University of Science and Technology Wuhan 430074, Hubei, China [email protected], [email protected] 2Department of Computer Science (Algorithms and Complexity) University of the Philippines Diliman 1101 Quezon City, Philippines [email protected] 3Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {mdelamor,marper}@us.es Abstract. Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. In this work, a discrete structure representation of SN P systems with extended rules and without delay is proposed. Specifically, matrices are used to represent SN P systems. In order to represent the computations of SN P systems by matrices, configuration vectors are defined to monitor the number of spikes in each neuron at any given configuration; transition net gain vectors are also introduced to quantify the total amount of spikes consumed and produced after the chosen rules are applied. Nondeterminism of the systems is assured by a set of spiking transition vectors that could be used at any given time during the computation. With such matrix representation, it is quite convenient to determine the next configuration from a given configuration, since it involves only multiplication and addition of matrices after deciding the spiking transition vector. 1 Introduction Membrane computing was initiated by P˘aun [6] and has developed very rapidly (already in 2003, ISI considered membrane computing as “fast emerging research area in computer science”, see http://esi-topics.com). It aims to abstract computing ideas (data structures, operations with data, computing models, etc.) from the structure and the functioning of single cell and from complexes of cells, such as tissues and organs, including the brain. The obtained models are distributed and parallel computing devices, called Psystems.For updated information about membrane computing, please refer to [8]. This work deals with a class of neural-like P systems, called spiking neural Psystems(SN P systems, for short) [3]. SN P systems were inspired by the neurophysiological behavior of neurons (in brain) sending electrical impulses along axons to other neurons, with the aim of incorporating specific ideas from spiking neurons into membrane computing. Generally speaking, in an SN P system the processing elements are called neurons and are placed in the nodes of a directed graph, called the synapse graph. The content of each neuron consists of a number of copies of a single object type, namely the spike.Eachneuronmay also contain rules which allow to remove a given number of spikes from it, or send spikes (possibly with a delay) to other neurons. The application of every rule is determined by checking the content of the neuron against a regular set associated with the rule. Representation of P systems by discrete structures has been one topic in the field of membrane computing. One of the promising discrete structures to represent P systems is matrix. Models with matrices as their representation have been helpful to physical scientists – biologists, chemists, physicists, engineers, statisticians, and economists – solving real world problems. Recently, matrix representation was introduced for represent a restricted form of cell-like P systems without dissolution (where only non-cooperative rules are used) [2]. It was proved that with an algebraic representation P systems can be easily simulated and computed backward (that is, to find all the configurations that produce a given one in one computational step). In this work, a matrix representation of SN P systems without delay is proposed, where configuration vectors are defined to represent the number of spikes in neurons; spiking vectors are used to denote which rules will be applied; a spiking transition matrix is used to describe the skeleton of a system; the transition net gain vectors are also introduced to quantify the total amount of spikes consumed and produced after the chosen rules are applied. With this algebraic representation, matrix transition can be used to compute the next configuration from a given one. In addition, we consider another variant of SN P systems, SN P systems with weights (WSN P systems, for short), which were introduced in [9]. In these systems, each neuron has a potential and a given threshold, whose values are real (computable) numbers. Each neuron fires when its potential is equal to its threshold; at that time, part of the potential is consumed and a unit potential is produced (a spike). The unit potential is passed to neighboring neurons multiplied with the weights of synapses. The weights of synapses can also be real (computable) numbers. This variant of SN P system allows real numbers to be computed by the system. AmatrixoverRCis defined to represent WSN P systems, where vectors are defined to represent the potentials in neurons and the application of rules. In particular, when the potential of a neuron is smaller than its spiking threshold, then this potential vanishes (the potential of the neuron is set to zero). Therefore, a forgetting vector is introduced to denote the potential vanishing from neurons. It is also shown that matrix representation is convenient for deciding the next configuration of the system from a given configuration. The rest of this paper is organized as follows. In the next section, the definition of SN P systems is introduced. In Section 3 the matrix representation of SN P systems is given, and an example is given to illustrate how to represent the computation of an SN P system by matrix transition. In Section 4 the matrix representation method is extended to WSN P systems. Conclusions and remarks are given in Section 5. 2 Spiking Neural P Systems In this section, a restricted variant of SN P systems, SN P systems without delay, is introduced. Definition 1. An SN P system without delay, of degree m≥1,isaconstruct of the form Π=(O,σ1,...,σ m,syn,in,out), where: 1. O={a}is the singleton alphabet (ais called spike); 2. σ1,...,σ mareneurons,oftheform σi=(ni,R i),1≤i≤m, where: a) ni≥0is the initial number of spikes contained in σi; b) Riis a finite set of rules of the following two forms: (1) E/ac→ap,whereEis a regular expression over a,andc≥1,p≥1, with the restriction c≥p; (2) as→λ,fors≥1, with the restriction that for each rule E/ac→ap of type (1) from Ri,as/∈L(E); 3. syn ={(i, j)|1≤i, j ≤m, i =j}(synapses between neurons); 4. in, out ∈{1,2,...,m}indicate the input and output neurons, respectively. The rules of type (1) are spiking (also called firing) rules, which are applied as follows. If the neuron σicontains kspikes, and ak∈L(E),k ≥c, then the rule E/ac→ap∈Rican be applied. This means that consuming (removing) cspikes (thus only k−cspikes remain in σi), the neuron is fired, and it produces pspikes; these spikes are transported to all neighbor neurons by outgoing synapses. If a rule E/ac→aphas E=ac,thenitiswritteninthesimplifiedformac→ap. The rules of type (2) are forgetting rules; they are applied as follows: if the neuron σicontains exactly sspikes, then the rule as→λfrom Rican be used, meaning that all sspikes are removed from σi. In each time unit, if a neuron σican apply one of its rules, then a rule from Rimust be applied. Since two spiking rules, E1/ac1→ap1and E2/ac2→ap2, can have L(E1)∩L(E2)=∅, it is possible that two or more rules are applicable in a neuron. In that case, only one of them is chosen and applied nondeterministically. However, note that, by definition, if a spiking rule is applicable, then no forgetting rule is applicable, and vice versa. Thus, the rules are applied in the sequential manner in each neuron, at most one in each step, but neurons function in parallel with each other. It is important to notice that the applicability of a rule is established based on the total number of spikes contained in the neuron. The configuration of the system is described by the number of spikes present in each neuron. 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 applied. The result of a computation is the number of steps elapsed between the first two spikes sent by the output neuron to the environment during the computation. 3 Matrix Representation of SN P Systems In this section, a matrix representation of SN P systems is given. Based on this representation, it is shown how the computation of SN P systems can be represented by operations with matrices. As mentioned in the above section, a configuration of the system is described by the number of spikes present in each neuron. Here, vectors are used to represent configurations. Definition 2 (Configuration Vectors). Let Πbe an SN P system with m neurons, the vector C0=(n1,n 2,...,n m)is called the initial configuration vector of Π,whereniis the amount of the initial spikes present in neuron σi, i=1,2,...,m before a computation starts. In a computation, for any k∈N, the vector Ck=(n(k) 1,n (k) 2,...,n (k) m)is called the kth configuration vector of the system, where n(k) iis the amount of spikes in neuron σi,i=1,2,...,m after the kth step of the computation. In order to describe which rules are chosen and applied in each configuration, spiking vectors are defined. Definition 3 (Spiking Vectors). Let Πbe an SN P system with mneurons and nrules, and Ck=(n(k) 1,n (k) 2,...,n (k) m)be the kth configuration vector of Π. Assume a total order d:1,...,n is given for all the nrules, so the rules can be referred as r1,...,r n.Aspiking vector s(k)is defined as follows: s(k)=(r(k) 1,r(k) 2,...,r (k) n), where: r(k) i=⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1,if the regular expression Eiof rule riis satisfied by the number of spikes n(k) j(rule riis in neuron σj)and rule riis chosen and applied; 0,otherwise. In particular, s(0) =(r(0) 1,r(0) 2,...,r (0) n)is called the initial spiking vector. The application of each rule will change the number of spikes in some neurons, for example, when the rule ri:E/ac→apis applied in neuron σj,itconsumes cspikes in σj,andemitspspikes; these pspikes are immediately delivered to all the neurons σssuch that (j, s)∈syn. Here, a spiking transition matrix is defined to denote the amount of spikes consumed (or received) by each neuron via each rule. Definition 4 (Spiking Transition Matrix). Let Πbe an SN P system with mneurons and nrules, and d:1,...,nbe a total order given for all the nrules. The spiking transition matrix of the system Π,MΠ,isdefinedasfollows: MΠ=[aij ]n×m, where: aij =⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ −c, if rule riis in neuron σjand it is applied consuming cspikes; p, if rule riis in neuron σs(s=jand (s, j)∈syn) and it is applied producing pspikes; 0,if rule riis in neuron σs(s=jand (s, j)/∈syn). In a spiking transition matrix, the row iis associated with the rule ri:E/ac→ ap. Assume that the rule riis in neuron σj. When the rule riis applied, it consumes cspikes in neuron σj;neuronσs(s=jand (j, s)∈syn) receives pspikes from neuron σj;neuronσs(s=jand (j, s)/∈syn) receives no spike from neuron σj. By the definition of spiking transition matrix, the entry in the position (i, j) is a negative number; the other entries in the row iare non-negative numbers. So the following observation holds: Observation 1: each row of a spiking transition matrix has exactly one negative entry. In a spiking transition matrix, the column iis associated with neuron σi.For an SN P system, without loss of generality, it can be assumed that each neuron has at least one rule inside (if a neuron has no rule inside, it just stores spikes, sending no spikes to other neurons or environment, so it can be deleted without any influence to the computational result of the system). Assume the rules in neuron σiare rm,rn,.... These rules consume spikes of neuron σiwhen they are applied. So the corresponding entries (m, i),(n, i),... in the spiking transition matrix are negative numbers, and the following observation holds: Observation 2: each column of a spiking transition matrix has at least one negative entry. In the following, it will be shown that how matrices representing SN P systems can be used to represent the computation of SN P systems by operating with matrices. Before the matrix operations for SN P systems are formally defined, a simple example is provided as follows. Example 1. Let us consider an SN P system Π=({a},σ 1,σ 1,σ 3,syn,out)that generates the set Nof natural numbers excluding 1,where σ1=(2,R 1), with R1={a2/a →a, a2→a};σ2=(1,R 2), with R2={a→a};σ3=(1,R 3), with R3={a→a, a2→λ};syn ={(1,2),(1,3),(2,1),(2,3)};out =3.Πis also represented graphically in Figure 1, which may be easier to understand. a 2 a 2 / a  a a 2  a a a  a a a  a a 2  1 2 3  1   2   3   4   5  Fig. 1. An SN P system Πthat generates the set N−{1} In order to represent the above SN P system Πin a matrix, a total order is set for all the rules in the system, which can be seen in Figure 1. With this order, the rules can be denoted by r1,...,r 5. Let MΠ1=[aij ]5×3be the spiking transition matrix for Π. By Definition 4, the row iof MΠis associated with the rule ri:E/ac→ap,c≥1,p≥0insystem Π.Theentriesai1,a i2,a i3are the amount of spikes which neurons σ1,σ 2,σ 3will get (or consume) when rule riis applied. The spiking transition matrix for the SN P system Πdepicted in Figure 1 is as follows. MΠ= ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ −11 1 −21 1 1−11 00−1 00−2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ (1) Initially, neurons σ1,σ2,andσ3have 2, 1, and 1 spike(s), respectively. According to Definition 2, the initial configuration vector for system Πwould be C0=(2,1,1). Since neuron σ1has two rules r1and r2that are applicable in the initial transition, one of the rules could be chosen, the initial spiking transition vector would be (1,0,1,1,0) or (0,1,1,1,0) by Definition 3. Note that the rule r5is not applicable because the regular expression a2is not satisfied in neuron σ3. If the rule r1:a2/a →ais applied, it consumes one spike in neuron σ1and sends one spike to neurons σ2and σ3, respectively; at the same time, neuron σ2 sends one spike to each of the neurons σ1and σ3. In this step, the net gain of neuron σ1is 0 spike (it consumes 1 spike by r1and receives 1 spike from neuron σ2); the net gain of neuron σ2is 0 spike (it consumes 1 spike by r3and receives 1 spike from neuron σ1); the net gain of neuron σ3is 1 spike (it consumes 1 spike by rule r5and receives 1 spike from each of the neurons σ1and σ2). After this step, the numbers of spikes in neurons σ1,σ2and σ3are 2, 1 and 2, respectively. The illustration above explained intuitively how an SN P system computes from one configuration to the succeeding one. In order to use matrix operations to represent it, the following definitions are needed: Definition 5 (Transition Net Gain Vector). Let Πbe an SN P system with mneurons and nrules, and Ck=(n(k) 1,n (k) 2,...,n (k) m)be the kth configuration vector of Π.Thetransition net gain vector at step kis defined as NG(k)= Ck+1 −Ck. Lemma 1. Let Πbe an SN P system with mneurons and nrules, d:1,...,n be a total order for the nrules, MΠthe spiking transition matrix of Π,ands(k) the spiking vector at step k. Then the transition net gain vector at step kcan be obtained by NG(k)=s(k)·MΠ.(2) Proof. Assume that MΠ=[aij ]m×n,s(k)=(r(k) 1,r(k) 2,...,r (k) n), and NG(k)= (g1,g 2,...,g m). Note that the spiking vector s(k)is a {0,1}-vector that identifies the rules that would be applied at step k.Thus,Σn i=1 r(k) iaij represents the total amount of spikes received and consumed by neuron σjafter applying the rules identified by s(k). Therefore, the net gain of neuron σjis gj=Σn i=1 r(k) iaij ,for all j=1,2,...,m.Thatis,NG(k)=s(k)·MΠ. Theorem 1. Let Πbe an SN P system with mneurons and nrules, d:1,...,n be a total order for the nrules, MΠthe spiking transition matrix of Π,Ckthe kth configuration vector, and s(k)the spiking vector at step k, then the configuration Ck+1 of Πcan be obtained by Ck+1 =Ck+s(k)·MΠ.(3) Proof. This results follows directly from the preceding Lemma. Let us go back to the example shown in Figure 1. Given the initial configuration vector C0=(2,1,1), the next configuration of system Πcan be computed as follows. If the rules r1,r 3,r 4are chosen to be applied, the spiking vector is s(0) = (1,0,1,1,0), and the next configuration is C1=(2,1,1) + (1,0,1,1,0) ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ −11 1 −21 1 1−11 00−1 00−2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ =(2,1,2).(4) In the next step, r1,r 3,r 5are chosen to be applied, the spiking vector is (1,0,1,0,1), and the next configuration is C2=(2,1,2) + (1,0,1,0,1) ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ −11 1 −21 1 1−11 00−1 00−2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ =(2,1,2),(5) where the transition net gain vector is NG =(1,0,1,0,1) ⎛ ⎜ ⎜ ⎜ ⎜ ⎝ −11 1 −21 1 1−11 00−1 00−2 ⎞ ⎟ ⎟ ⎟ ⎟ ⎠ =(0,0,0).(6) Equation (6) means that the configuration of the system remains unchanged as long as the rules r1,r3and r5are chosen to be applied. However, at any moment, starting from the first step of computation, neuron σ1can choose to apply the rule r2:a2→a. In this case, system will go to another configuration. The checking is left to the readers. The following Corollary is a direct consequence of the preceding Theorem. Corollary 1. Let Πbe an SN P system with mneurons and nrules, d:1,...,n be a total order for the nrules, MΠthe spiking transition matrix of Π,Ckthe kth configuration vector, and s(k−1) the spiking vector at step k−1, then the previous configuration Ck−1is Ck−1=Ck−s(k−1) ·MΠ.(7) In the above matrix representation, the spikes sent to the environment are not considered. In order to consider the spikes sent to the environment, an augmented spiking transition matrix is introduced. Definition 6 (Augmented Transition Spiking Matrix). Let Πbe an SN P system with mneurons and nrules, d:1,...,n be a total order for the nrules, and MΠthe n×mspiking transition matrix of Π.Anaugmented spiking transition matrix is defined as [MΠ|e]n×(m+1), where the column e=(e1,e 2,...,e n)Trepresents the spikes sent to the environment, with: ei=p, if rule riis in the output neuron and it is applied producing pspikes; 0,if rule riis not in the output neuron. Correspondingly, the augmented configuration vector after the kth step in the computation is defined as Ck=(n(k) 1,n (k) 2,...,n (k) m,n (k) e), where n(k) iis the amount of spikes in neuron σi, for all i=1,2,...,m,n(k) eis the amount of spikes collected in the environment. Using this vector instead of the configuration vector in Definition 2 allows us to monitor the output of the system. 4 Matrix Representation for WSN P Systems In this section, matrix representation for spiking neural P systems with weights (WSN P systems, for short) is investigated. Instead of counting spikes as in usual SN P systems, each neuron in WSN P systems contains a potential, which canbeexpressedbyacomputablerealnumber. Each neuron fires when its potential is equal to the given threshold. The execution of a rule consumes part of the potential and produces a unit potential. This unit potential passes to neighboring neurons multiplied with the weights of synapses. In an SN P system with weights, the involved numbers – weights, thresholds, potential consumed by each rule – can be real (computable) numbers. Formally, the system is defined as follows. Definition 7. An SN P system with weights, of degree m≥1,isaconstructof the form Π=(σ1,...,σ m,syn,in,out), where: 1. σ1,...,σ mare neurons of the form σi=(pi,R i),1≤i≤m, where: a) pi∈Rcis the initial potential in σi; b) Riis a finite set of rules of the form Ti/ds→1,s=1,2,...,n ifor some ni≥1,whereTi∈Rc,Ti≥1, is the firing threshold potential of neuron σi,andds∈Rcwith the restriction 0<d s≤Ti; 2. syn ⊆{1,2,...,m}×{1,2,...,m}×Rcare synapses between neurons, with i=j,w=0for each (i, j, w)∈syn, 1≤i, j ≤m; 3. in, out ∈{1,2,...,m}indicate the input and output neurons, respectively.