Weighted Fuzzy Spiking Neural P Systems

Weighted Fuzzy Spiking Neural P Systems Jun Wang, Peng Shi, Senior Member, IEEE, Hong Peng, Mario J. P´erez-Jim´enez, and Tao Wang Abstract Spiking neural P systems (SN P systems) are a new class of computing models inspired by the neurophysiological be-havior of biological spiking neurons. In order to make SN P sys-tems capable of representing and processing fuzzy and uncertain knowledge, we propose a new class of spiking neural P systems in this paper called weighted fuzzy spiking neural P systems (WFSN P systems). New elements, including fuzzy truth value, certain factor, weighted fuzzy logic, output weight, threshold, new firing rule, and two types of neurons, are added to the original definition of SN P systems. This allows WFSN P systems to adequately characterize the features of weighted fuzzy production rules in a fuzzy rule-based system. Furthermore, a weighted fuzzy backward reasoning algorithm, based on WFSN P systems, is developed, which can ac-complish dynamic fuzzy reasoning of a rule-based system more flexibly and intelligently. In addition, we compare the proposed WFSN P systems with other knowledge representation methods, such as fuzzy production rule, conceptual graph, and Petri nets, to demonstrate the features and advantages of the proposed tech-niques. Index Terms Spiking neural P systems (SN P systems), weighted fuzzy production rules, weighted fuzzy reasoning, weighted fuzzy spiking neural P systems (WFSN P systems). I. INTRODUCTION NATURAL Computing is a novel field of computer science research that uses computational paradigms inspired from various well-known natural phenomena in physics, chemistry, and biology. There are several fields in Natural Computing that are now well established, such as genetic algorithms [1], [2], artificial neural networks [3]–[6], particle swarm optimization [7]–[11], DNA-based molecular computing [12]. Membrane computing, which is part of molecular computing, was introduced in [13] under the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. Since then, a large number of variants have been considered, and the devices of the models are generally called P systems [14]. A new class of distributed and parallel computing devices, spiking neural P systems (SN P systems), presented in [15], was inspired by the neurophysiological behavior of neurons sending electrical impulses (spikes) along axons to other neurons. An SN P system can be viewed as a set of neurons placed in the nodes of a directed graph whose arcs represent the synaptic connections among the neurons, and each neuron contains a number of copies of single object type as well as a lot of firing/spiking and forgetting rules. The rules in each neuron are used in a sequential manner, but neurons function with each other in parallel. More recently, a large number of variants of SN P systems have been developed (see, [16]–[23] and the references therein). In addition to distributed and parallel computing abilities, SN P systems inherently feature: 1) high understandability (due to their directed graph structure); 2) dynamic behavior (it seems to be suitable to model dynamic behaviors of a system on the basis of neuron’s firing/spiking mechanisms); 3) synchronization (it seems to be suitable to describe concurrent events or activities); 4) nonlinearity (it is capable of dealing with nonlinear problem); and 5) nondeterministic. No doubt, these features will be attractive to a lot of real-world problems, such as process control, expert systems, fault diagnosing, investment advising systems, and even the new intelligent wireless sensor networks. However, many successful applications have determined that there is a great deal of fuzzy and uncertain information in the aforementioned real-world areas and our computing models are often required to be capable of dealing with fuzzy and uncertain knowledge. It is well known that fuzzy knowledge retrieved by human experts or extracted by fuzzy neural networks (FNNs) is usually represented by fuzzy production rules [24]–[27]. Nevertheless, fuzzy production rules are not straightforward and their fuzzy reasoning is usually a complicated process. For this reason, some knowledge representation methods were developed, such as conceptual graph [28], semantic networks [29], and fuzzy Petri nets [30]–[33]. Meanwhile, weighted fuzzy production rules and weighted fuzzy logics were developed in order to process fuzziness and uncertainty in the knowledge base [34]–[39]. As stated previously, some significant features possessed by SN P systems are attractive to real-world applications. Unfortunately, existing SN P systems and their variants lack the ability to process fuzzy and uncertain knowledge so far. The main motivation behind our study is to build a bridge between SN P systems and various real-world problems such that the SN P systems can serve as a new model in real-world problems. For this reason, we will extend SN P systems so that they are capable of dealing with fuzzy and uncertain information and representing weighted fuzzy production rules. In this paper, we propose weighted fuzzy spiking neural P systems (WFSN P systems) by incorporating some new elements into the original definition of SN P systems, including a new type of neuron, fuzzy truth value, certain factor, weighted fuzzy logic, output weight, threshold, and new firing/spiking rules. WFSN P systems are especially suitable from expressing weighted fuzzy production rules in graphical form. In addition, a fuzzy backward reasoning algorithm, based on the WFSN P systems, is developed. The main advantages offered by the proposed WFSN P systems can be summarized as follows. 1) Because of the graphical nature of WFSN P systems, the structure of weighted fuzzy production rules in a fuzzy knowledge base can be easily modeled and visualized, and the model is relatively simple and legible. 2) ThedynamicfiringmechanismofneuronsinWFSNPsystems are capable of carrying out dynamic fuzzy reasoning process more intelligently. 3) Based on the parallel computing mechanism of WFSN P systems, the proposed reasoning algorithm is an efficient reasoning algorithm with parallel reasoning ability. The rest of this paper is organized as follows. In Section II, we provide the original definition of SN P systems, and propose WFSN P systems and simplified versions. In Section III, we perform weighted fuzzy knowledge representation based on the WFSN P systems. A fuzzy backward reasoning algorithm based on WFSN P systems for a rule-based system is presented in Section IV. In Section V, we compare WFSN P systems with other knowledge representation methods to show the advantages of our results. Finally, Section VI gives the conclusions. II. WEIGHTED FUZZY SPIKING NEURAL PSYSTEMS A. Spiking Neural P Systems In this section, we briefly review SN P systems in standard form and in a computing version (i.e., able to take an input and provide an output). (A more detailed description of SN P systems can be found in [16]–[22]). Definition 1: A computing SN P system of degree m≥1isa construct of the form Π=(O,σ1,...,σ m,syn,in,out) where 1) O={a}singleton alphabet (the object ais called spike); 2) σ1,...,σ mneurons, of the form σi=(ni,ri)with 1 ≤ i≤m, where: a) ni≥0 initial number of spikes contained in neuron σi; b) rifinite set of rules of the following two forms: 1) E/ac→a;d, where Eis a regular expression over a, and c,d≥0 are natural numbers; 2) as→λ, where s≥1 is a natural number, with restriction that for each rule E/ac→a;dof type (i) from ri,wehaveas∈ L(E); 3) syn ⊆{σ1,σ 2,...,σ m}×{σ1,σ 2,...,σ m}with i=j for all (σi,σ j)∈syn, 1 ≤i, j ≤m(synapses between neurons); 4) in,out ∈{σ1,σ 2,...,σ m}input and output neurons, respectively. In the aforementioned definition, the rule of type (1) is called the firing/spiking rule, and that of type (2) is called the forgetting rule. The firing mechanism of neurons in SN P systems can be described as follows. If a neuron σicontains k spikes, ak∈L(E)and k≥c, the firing/spiking rule E/ac→ a;d∈riin neuron σiis enabled and can be applied. This means that cspikes are consumed, k−cspikes remain in the neuron, the neuron fires, and then it produces a spike after dtime units. If d=0, the spike is emitted immediately. In the case d≥1, if theruleisusedatstept, the neuron is “closed” and “blocked” at steps t, t +1,...,t+d−1, and it cannot receive new spikes from other neurons. At step (t+d), the neuron emits a spike and becomes again open; hence, other neurons can receive the spike. The spike emitted by neuron σiis replicated and it goes to all neurons σjsuch that (σi,σ j)∈syn (each such neuron σjof those receives a spike). A forgetting rule ac→λis applicable to a neuron whether the neuron contains exactly cspikes, and then, all cspikes are removed. Note that if all rules of a system have d=0, i.e., no delay is involved, the parameter dis omitted. SN P systems are synchronized because a global clock is assumed, marking the time for the whole system. Besides, SN P systemsarenondeterministic because tworulesE1/ac1→a;d1 and E2/ac2→a;d2can have L(E1)∩L(E2)=∅. Therefore, it is possible that two or more rules of the system can be enabled in a neuron. In this case, one of them is nondeterministically chosen to be used. Moreover, in each time unit, if a neuron can use a rule, the rule must be used. Each neuron deals with its spikes in a sequential manner, only using one rule in each time unit, but the rules are used in parallel for all neurons of the system. An instantaneous description or a configuration at any instant of an SN P system is described by both the number of spikes in each neuron and the state of the neuron, or more precisely, by the number of steps to count down until it becomes open (this number is zero if the neuron is already open). The initial configuration is described by the number of spikes initially placed in each neuron, n1,n 2,...,n m, with all neurons being open. A configuration is a halting configuration if all neurons are open and no rule of the system is applicable to it. Using the rules described previously, one can define transitions among configurations. We say that configuration C1yields configuration C2 in one transition step, which is denoted by C1⇒ΠC2,ifwe can pass from C1to C2by applying the rules from the system following the previous remarks. Acomputation of Πis a (finite or infinite) sequence of configurations such that: 1) the first term of the sequence is the initial configuration of the system; 2) each noninitial configuration of the sequence is obtained from the previous configuration by a transition step; 3) if the sequence is finite (called halting computation), then the last term of the sequence is a halting configuration. With any computation (halting or not), we can associate a spike train, which is a 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. In addition, we can also associate other forms of computation results according to different computing purposes, such as the distance between two consecutive steps when there are spikes that exit the system. B. Weighted Fuzzy Spiking Neural P Systems The introduction of fuzzy elements in P systems is an interesting and open issue. This paper will pay attention to this issue but be limited to the discussion of SN P systems for processing fuzzy and uncertain knowledge. Thus, we will extend the definition of SN P systems and propose a class of extended SN P system models, called WFSN P systems. The motivation for this is to model weighted fuzzy production rules in a fuzzy knowledge base and perform weighted fuzzy reasoning by using WFSN P systems in a more intelligent manner. Definition 2: A computing WFSN P system of degree m≥1 is a construct of the form Π=(O,Np,N r,syn,IN,OUT) where 1) O={a}singleton alphabet (the object ais called spike); 2) Np={σp1,σ p2,...,σ pm}proposition neuron set, where σpi is its ith proposition neuron associated with a fuzzy proposition in a fuzzy knowledge base, 1 ≤i≤m. Each proposition neuron σpi has the form σpi =(αi,ωi,λi,ri), where a) αi∈[0,1]potential value of pulse contained in proposition neuron σpi.αiis used to express fuzzy truth value of a proposition associated with proposition neuron σpi. b) ωi=(ωi1,ω i2,...,ω isi)output weight vector of the neuron σpi, where component ωij ∈[0,1] is the weight on jth output synapse (arc) of the neuron, 1 ≤j≤si, and siis the number of all output synapses (arc) of the neuron. c) rifinite set of firing/spiking rules of the form E/aα→aα;d, where α∈[0,1], and d≥0isa natural number. E={α≥λi}is called the firing condition, i.e., if α≥λi, then the firing rule will be enabled, where λi∈[0,1)is called the firing threshold. 3) Nr={σr1,σ r2,...,σ rn}ruleneuron set, where σri is its ith rule neuron associated with a weighted fuzzy production rule in a fuzzy knowledge base, 1 ≤i≤n. Each rule neuron σri has the form σri =(αi,γ i,νi,τ i,ri), where a) αi∈[0,1]potential value of pulse contained in rule neuron σri. b) γi∈[0,1]certain factor. It represents the strength of beliefofaweightedfuzzyproductionruleassociated with rule neuron σri. c) νi=(νi1,ν i2,...,ν iti)output weight vector of the neuron σri, where component νij ∈[0,1]is the weight on jth output synapse (arc) of the neuron, 1 ≤j≤ti, and tiis the number of all output synapses (arc) of the neuron. d) rifinite set of firing/spiking rules of the form E/aα→aβ;d, where α∈[0,1],β∈[0,1], and d≥0 is a natural number. E={α≥τi}is called the firing condition, i.e., if α≥τi, then the firing rule will be enabled, where τi∈[0,1)is called the firing threshold. 4) syn ⊆(Np×Nr)(Nr×Np)synapses between both proposition neurons and rule neurons. Note that there are no synapse connections between any two proposition neurons or between any two rule neurons; 5) IN,OUT ⊆Npinput neuron set and output neuron set, respectively. In the following, we illustrate how WFSN P systems are extended from the original definition of SN P systems. First, WFSN P systems consist of two types of neurons: proposition neurons and rule neurons. The intuitive purpose of introducing the two types of neurons is to express fuzzy propositions and weighted fuzzy production rules in a fuzzy knowledge base. Second, content of the neuron is now denoted by a fuzzy truth value instead of the number of spikes as in SN P systems. It can be interpreted as the (potential) value of spike from the viewpoint of biological neuron. For a proposition neuron, its content is used to express the fuzzy truth value of a fuzzy proposition associated with it. When a neuron fires and emits a spike, the (potential) value of the spike is transmitted into all successive neuronsconnected with the neuron. Third, eachproposition neuron is assigned an output weight vector ω =(ω1,ω 2,...,ω s). This indicates that the jth output synapse of the proposition neuron has the output weight ωj. Therefore, when a proposition neuron fires and emits a spike with value α, its jth successive neuron will receive a spike with value α⊗ωjfrom its output synapse, where “⊗” is the multiplication operator of fuzzy truth values. Similarly, each rule neuron is also assigned an output weight vector ν =(ν1,ν 2,...,ν t). When a rule neuron fires and emits a spike with value α, its jth successive neuron will receive a spike with value (ανj)⊗γ, where “” is the division operator of fuzzy truth values. Fourth, because proposition neurons and rule neurons in WFSN P systems are used to characterize fuzzy propositions and weighted fuzzy production rules in a fuzzy knowledge base, respectively, both input neuron set and output neuron set only consist of proposition neurons, while rule neurons are interconnector of proposition neurons. Moreover, there are no direct connections between two proposition neurons or between two rule neurons. Fifth, WFSN P systems use the new firing condition E={α≥λi}or E={α≥τi} rather than the original regular expression in SN P systems, and this controls whether the corresponding neuron fires or not. If a proposition neuron contains at least a spike and its value of spike is with α≥λi, then it fires. Likewise, if a rule neuron contains at least a spike and its value of spike is with α≥τi, then it fires. Finally, when a neuron receives spikes from its several predecessor neurons, (potential) values of the received Fig. 1. Proposition neuron in S-WFSN P systems. Fig. 2. Rule neuron in S-WFSN P systems. spikes will be calculated by using some logical operators unlike the neuron in SN P systems that simply accumulate the number of spikes received by it. The proposition neuron calculates (potential) values of spikes received by it from its predecessor neurons through logical “OR” operator “∨,” whereas rule neuron calculates potential values of spikes received by it through addition operator “⊕” (see Figs. 1 and 2). In addition to several aspects described previously, other original mechanisms in SN P systems are retained in WFSN P systems, for instance, time delay d, synchronization, nondeterminacy, and so forth. As stated previously, the purpose of proposing the WFSN P systems is to model weighted fuzzy production rules in a knowledge base and develop a more intelligent weighted fuzzy reasoning algorithm. Some elements in WFSN P systems however, are redundant, such as time delay d, and firing thresholds λiand τi. Hence, we simplify the WFSN P systems by removing the redundant elements and denote the simplified version of WFSN P systems as S-WFSN P systems. Compared with WFSN P systems, S-WFSN P systems have the following differences. First, time delay dis omitted; hence, all neurons are always open in S-WFSN P systems. Second, firing thresholds λiand τiin WFSN P systems are removed. Therefore, if a neuron contains at least a spike and its value of spike αi>0, then it fires. Third, any neuron (proposition neuron or rule neuron), contains only a firing rule. Finally, each rule neuron has only an output weight factor νi, i.e., all its output synapses are assigned the same weight. We describe the operating principle of S-WFSN P systems as follows. Initially, the system provides a spike for each input neuron in IN (or each input neuron in IN receives a spike from the environment as its input), where the value of the spike equals the fuzzy truth value of the corresponding proposition. When the system halts, the contents contained in output neurons (or results exported by output neurons) are regarded as its computing results. In S-WFSN P systems, each neuron contains only a firing/spiking rule and its firing principle is explained as follows. First, if a proposition neuron has kpredecessor rule neurons and it receives kspikes from them, the (potential) value of the received kspikes is calculated as its content αthrough Fig. 3. Example of S-WFSN P systems: Π0. logical “OR” operator “∨.” When α>0, the neuron fires and its firing/spiking rule E/aα→aαcan be applied. Applying the firing/spiking rule E/aα→aαmeans that the spike contained in the neuron is consumed, and then, it produces a spike with value α, which will be weighted by the corresponding weight factor. In this paper, we denote a proposition neuron by a circle, as shown in Fig. 1. Here, α=x1∨x2∨...∨xk, and its outputs are α⊗ωi(i=1,2,...,s), respectively. Second, if a rule neuron has kpredecessor proposition neurons, then it fires and its firing/spiking rule E/aα→aβcan be applied when it receives kspikes from its all predecessor proposition neurons. The value of the received kspikes is calculated as its content αthrough addition operator “⊕.” Applying the firing/spiking rule E/aα→aβmeans that the spike contained in the neuron is consumed, and then, it produces a spike with value βwhere β=(αν)⊗γ. In this paper, we denote a rule neuron by a rectangle, as shown in Fig. 2. Here, α=x1⊕x2⊕...⊕xk, and all its outputs are (αν)⊗γ. Example 1: Fig. 3 shows an example of S-WFSN P systems, which can be formally described as follows. Π0=({a}, {σp1,σ p2,σ p3,σ p4,σ p5},{σr1,σ r2,σ r3,σ r4},syn,IN,OUT), where 1) σpj =(αj,ω j,r j)(j=1,...,5)proposition neurons. The weights of proposition neurons σp1,σ p3, and σp4 are ω1=1.0,ω 3=0.8, and ω4=0.7, respectively, while proposition neuron σp2has two weights ω21 =1.0 and ω22 =1.0; 2) σri =(αi,γ i,ν i,r i)(j=1,...,4)rule neurons. The certain factors of rule neurons σr1,σ r2,σ r3, and σr4are γ1=0.85,γ 2=0.90,γ 3=0.95, and γ4=0.90, respectively. The weights of rule neurons σr1,σ r2,σ r3, and σr4 are ν1=ω1=1.0,ν 2=ω22 =1.0,ν 3=ω21 =1.0, and ν4=ω3⊕ω4=1.5, respectively; 3) syn={(σp1,σ r1),(σp2,σ r2),(σp2,σ r3),(σp3,σ r4),(σp4, σr4),(σr1,σ p2),(σr2,σ p3),(σr3,σ p4),(σr4,σ p54)}; 4) IN ={σp1}, OUT ={σp5}. In addition to modeling weighted fuzzy production rules by using WFSN P systems, we will develop a fuzzy reasoning algorithm based on WFSN P systems in this paper. In order to conveniently describe our weighted fuzzy reasoning algorithm, we first, define several concepts (terminologies) here. Let σrs TABLE I IMMEDIATE RULE-INCIDENCE TABLE OF ALL PROPOSITION NEURONS IN EXAMPLE 1 be a rule neuron and σpi,σpj, and σpk be three proposition neurons. Definition 3: Immediately backward rule incidence.If (σpi,σ rs)∈syn and (σrs,σ pk)∈syn, i.e., σrs is the interconnector between σpi and σpk, then σpi is called an immediately backward rule incidence of σpk. In Example 1, σp1is an immediately backward rule incidence of σp2, and σp2is an immediately backward rule incidence of σp3and σp4, while σp3and σp4are immediately backward rule incidences of σp4. Definition 4: Backward rule incidence.Ifσpi is an immediately backward rule incidence of σpj, and σpj is an immediately backward rule incidence of σpk, then σpi is called a backward rule incidence of σpk. From Example 1, we can observe that σp1is a backward rule incidence of σp3and σp4, respectively. Moreover, σp2is a backward rule incidence of σp5. Definition 5: Immediately backward rule incidence set.For a proposition neuron σpk, its immediately backward rule incidence set is defined as follows: IBRIS(σpk)={σpi ∈Np|σpi is an immediately backward rule incidence of σpk}. Definition 6: Immediately backward rule incidence table.For WFSNPsystems,itsimmediatelybackwardrule incidence table is defined as follows: IRIT={(σpk,IBRIS(σpk),σ ri)|for ∀σpk ∈Npand ∀σpj ∈ IBRIS(σpk),∃σri ∈Nrsuch that (σpj,σ ri)∈syn and (σri, σpk)∈syn}. For Example 1, Table I gives the immediately backward rule-incidence table of Π0. From Table I, we can see that IBRIS(σp2)={σp1}, IBRIS(σp3)={σp2}, IBRIS(σp4)= {σp2}, while IBRIS(σp5)={σp3,σ p4}, where σp3and σp4are adjacent proposition neurons with respect to rule neuron σr4. III. WEIGHTED FUZZY KNOWLEDGE REPRESENTATION A. Weighted Fuzzy Production Rules The weighted fuzzy production rules that are discussed here are similar to conventional fuzzy production rules. However, a weight factor (or vector) is assigned to each proposition in the antecedent part in a fuzzy production rule, and a certainty factor is also assigned to the rule. Weight factor of a proposition indicates the degree of its importance contributing to the consequent when comparing with other proposition in the antecedent part. Obviously, when there is only one proposition in the antecedent of a fuzzy production rule, weight is meaningless for the rule. Generally, weighted fuzzy production rules can be categorized into four types as follows: Type 1: Ri:IFpjTHEN pk(CF =γi), ω. This type rule is a simple fuzzy production rule. In the rule Ri, pjand pkare propositions, γiis certainty factor of the rule, and ωis the weight of proposition pj. Since pjis only one proposition in the antecedent part of the rule Ri, its weight ωis meaningless for the rule. Therefore, we can set ω=1. Type 2: Ri:IFp1AND p2AND ... AND pk−1THEN pk (CF =γi), ω1,ω 2,...,ω k−1 where ω1,ω 2,...,ω k−1are the weights of propositions p1,p 2,...,p k−1in the antecedent part of the rule Ri, respectively. This is a composite conjunctive fuzzy production rule. Type 3: Ri:IFp1THEN p2AND p3AND ... AND pk (CF =γi), ω where ωis the weight of proposition p1in the antecedent part of the rule Ri. Similarly, we can set ω=1 since weight ωin the rule is meaningless. Type 4: Ri:IFp1OR p2OR ... OR pk−1THEN pk (CF =γi), ω1,ω 2,...,ω k−1. This is a composite disjunctive fuzzy production rule. In the rule Ri,ω1,ω 2,...,ω k−1are the weights of propositions p1,p 2,...,p k−1in the antecedent part of the rule Ri, respectively. B. Mapping Weighted Fuzzy Production Rules Into Weighted Fuzzy Spiking Neural P Systems In order to model weighted fuzzy production rules in a fuzzy knowledge base by using S-WFSN P systems, we have to map the aforementioned weighted fuzzy production rules into S-WFSN P systems. The basic principle is to map each fuzzy proposition in fuzzy knowledge base into one proposition neuronofS-WFSNPsystemsand to map each fuzzy production rule into one rule neuron or several rule neurons. Thus, the weighted fuzzy production rules of four types described previously and their fuzzy reasoning processes can be modeled as follows. For a rule of Type 1, assume that the fuzzy truth value of propositions pjis αjand certainty factor of the rule is γi. Hence, the rule of Type 1 can be modeled by the following S-WFSN P system Π1, as shown in Fig. 4(a): Π1=({a},{σpj,σ pk},{σri},syn,IN,OUT), where 1) σpj andσpk twopropositionneuronsassociatedwith fuzzy propositions pjand pk, respectively. σpj =(αj,ω j,r j) and σpk =(αk,ω k,r k). Since the antecedent part of the rule has only one proposition, set ωj=1; 2) σri rule neuron associated with the fuzzy production rule Ri.σri =(αi,γ i,ν i,r i), where νi=1; 3) syn ={(σpj,σ ri ),(σri,σ pk )},IN ={σpj},OUT = {σpk}. Furthermore, Fig. 4(a) shows the dynamic fuzzy reasoning process modeled by Π1. The fuzzy reasoning process is (b) (c) (d) (a) …… … Fig. 4. Four weighted fuzzy rule presentations with S-WFSN P systems and their rule reasoning. (a) Type 1. (b) Type 2. (c) Type 3. (d) Type 4. automatically carried out via three time units. Initially, a spike with value αjis assigned into proposition neuron σpj. Thus, σpj fires and emits a spike with value αj. Next, rule neuron σri receives the spike and fires, and then, it sends a spike with value αj⊗γito proposition neuron σpk. Finally, proposition neuron σpk receives the spike and its value of spike αj⊗γiis regarded as the result computed by the S-WFSN P system Π1,asshown in Fig. 4(a). For a rule of Type 2, assume that the fuzzy truth values of propositions p1,p2,...,pk−1are α1,α2,...,αk−1, respectively, and certainty factor of the rule is γi. Hence, the rule of Type 2 can be modeled by the following S-WFSN P system Π2,as shown in Fig. 4(b): Π2=({a},{σp1,...,σ pk−1,σ pk},{σri},syn,IN,OUT), where 1) σp1,σp2,...,σpk−1, and σpk proposition neurons associated with fuzzy propositions p1,p2,...,pk−1, and pk, respectively. σpj =(αj,ω j,r j),j=1,2,...,k− 1,k.ω1,ω 2,...,ω k−1are weights of the propositions p1,p 2,...,p k−1in the antecedent part of the rule, respectively; 2) σri rule neuron associated with the fuzzy production rule Ri.σri =(αri,γ i,ν i,r i), where νi=ω1⊕ω2⊕...⊕ ωk−1; 3) syn ={(σp1,σ ri),...,(σpk−1,σ ri),(σri,σ pk)}, IN ={σp1,σ p2,...,σ pk−1}, OUT ={σpk}. Fig. 4(b) shows the dynamic fuzzy reasoning process modeled by Π2. The fuzzy reasoning process is automatically performed as follows. Initially, a spike is provided for each proposition neuron σpj in IN and their values are α1,α 2,...,α k−1, respectively. These proposition neurons concurrently fire, and then, each of them emits a spike with value αj⊗ωj.Next, rule neuron σri receives spikes from these proposition neurons and values of the spikes are computed by addition operator “⊕” as its content, i.e., αri =(α1⊗ω1)⊕(α2⊗ω2)⊕...⊕ (αk−1⊗ωk−1). Thus, the rule neuron fires, and then, it sends a spike with value [αri νi]⊗γito proposition neuron σpk. Finally, proposition neuron σpk will receive the spike as its content, as shown in Fig. 4(b). Therefore, the result computed by Π2is αk={[(α1⊗ω1)⊕(α2⊗ω2)⊕...⊕ (αk−1⊗ωk−1)] (ω1⊕ω2⊕...⊕ωk−1)}⊗γi. For a rule of Type 3, assume that the fuzzy truth value of propositions p1is α1and certainty factor of the rule is γi. Hence, the rule of Type 3 can be modeled by the following S-WFSN P system Π3, as shown in Fig. 4(c): Π3=({a},{σp1,...,σ pk−1,σ pk},{σri},syn,IN,OUT), where 1) σp1,σp2,...,σpk−1, and σpk proposition neurons associated with fuzzy propositions p1,p2,...,pk−1, and pk,respectively. σp1=(α1,ω 1,r 1). Since p1is only one proposition in the antecedent part of the rule, set the weight ω1=1; 2) σri rule neuron associated with the fuzzy production rule Ri.σri =(αri,γ i,ν i,r i), where νi=1; 3) syn ={(σp1,σ ri),(σri,σ p2),(σri,σ p3),...,(σri,σ pk)}, IN ={σp1}, OUT ={σp2,σ p3,...,σ pk}. Fig. 4(c) shows dynamic fuzzy reasoning process modeled by Π3. The fuzzy reasoning process is automatically performed as follows. Initially, a spike is provided for proposition neuron σp1and its values is α1. Thus, the proposition neuron fires, and then, it emits a spike with value α1. Next, rule neuron σri receives the spikes and fires, and then, it sends a spike with value α1⊗γito its all successive proposition neurons. Finally, proposition neurons σp2,σ p3,...,σ pk will receive the spike as their contents, as shown in Fig. 4(c). Therefore, the results computed by Π3are α2=α1⊗γi,α3=α1⊗γi,..., αk=α1⊗γi. For a rule of Type 4, assume that fuzzy truth values of propositions p1,p2,...,pk−1are α1,α2,...,αk−1, respectively, and the certainty factor of the rule is γi. Hence, the rule of Type 4 can be modeled by the following S-WFSN P system Π4,as shown in Fig. 4(d): Π4=({a},{σp1,...,σ pk−1,σ pk},{σri},syn,IN,OUT), where 1) σp1,σp2,...,σpk−1, and σpk proposition neurons associated with fuzzy propositions p1,p2,...,pk−1, and pk respectively. σpj =(αj,ω j,r j),j=1,2,...,k−1,k. ω1,ω 2,...,ω k−1are the weights of the propositions p1,p 2,...,p k−1in the antecedent part of the rule, respectively; 2) σr1,σ r2,...,σ rk−1rule neurons associated with the fuzzy production rule Ri.σrj =(αrj,γ i,ν i,r j),j = 1,2,...,k−1, where νi=ω1⊕ω2⊕...⊕ωk−1; 3) syn ={(σp1,σ r1),(σp2,σ r2),...,(σpk−1,σ rk−1),(σr1, σpk),...,(σrk−1,σ pk)},IN={σp1,σ p2,...,σ pk−1}, OUT ={σpk}. Fig.4(d)showsthedynamicfuzzyreasoningprocess modeled by Π4. The fuzzy reasoning process is automatically performed as follows. Initially, a spike is provided for each proposition neuron σpj in IN and their values are α1,α 2,...,α k−1, respectively. These proposition neurons σpj concurrently fire, and then, each of them emits a spike with value αj⊗ωjinto the corresponding rule neuron σrj,j=1,2,...,k−1. Next, each rule neuron σrj receives the corresponding spike and fires, and then, it sends a spike with value [(αj⊗ωj)νi]⊗γi to proposition neuron σpk. Finally, proposition neuron σpk receives the spikes from the rule neurons, and the value of the spikes is computed by logical “OR” operator “∨” as its content, i.e., αk={[(α1⊗ω1)νi]⊗γi}∨{[(α2⊗ω2) νi]⊗γi}∨...∨{[(αk−1⊗ωk−1)νi]⊗γi}. Therefore, the result computed by Π4is αk={[(α1⊗ω1)(ω1⊕ω2 ⊕...⊕ωk−1)] ∨[(α2⊗ω2)(ω1⊕ω2⊕...⊕ωk−1)] ∨...∨[(αk−1⊗ωk−1)(ω1⊕ω2⊕...⊕ωk−1)]}⊗γi. As is well-known, fuzzy production rules are not straightforward and their fuzzy reasoning is usually a complicated process. However, from the aforementioned discussions, we can see that the structure of weighted fuzzy production rules modeled by the proposed WFSN P systems is visual and is easily comprehended due to its graphical nature. Moreover, owing to the parallel computing ability of WFSN P systems and the neuron’s firing mechanism, the proposed WFSN P systems are able to complete fuzzy reasoning process concurrently and automatically, and the computing process only takes three time units. IV. WEIGHTED FUZZY REASONING ALGORITHM In this section, we will present a weighted fuzzy reasoning algorithm based on S-WFSN P systems. From the previous discussion, we know that for a fuzzy knowledge base, proposition neurons express its all fuzzy propositions, while rule neurons model its weighted fuzzy production rules. Generally, we should provide the fuzzy truth values for a part of fuzzy propositions before reasoning, and the proposition neurons associated with the part of fuzzy propositions are in fact input neurons of the S-WFSN P system model. The goal of fuzzy reasoning method is to reason out the fuzzy truth values of other unknown fuzzy propositions (proposition neurons) from known fuzzy propositions (input neurons). These unknown fuzzy propositions are associated with output neurons of the S-WFSN P system model. Suppose we modeled the weighted fuzzy production rules of a fuzzy knowledge base by an S-WFSN P system model Π. Based on S-WFSN P systems, we developed a weighted fuzzy reasoning algorithm, which is called the weighted fuzzy backward reasoning algorithm. The basis of the weighted fuzzy backward reasoning algorithm is the construction of a fuzzy “⊕-OR” (Addition-OR) tree, which is similar to the algorithm in [40]. The tree uses a special data structure, i.e., a triple (σpk,IBRIS(σpk),α(σpk)) is used to express a node in the tree, where σpk is the kth proposition neuron, IBRIS(σpk)is its immediately backward rule incidence set of σpk, and α(σpk)is the fuzzy truth value of σpk. The weighted fuzzy backward reasoning algorithm (Algorithm 1) consists of three components: 1) building the immediately backward rule-incidence table IRIT (Algorithm 2); 2) generating fuzzy “⊕-OR” tree (Algorithm 3); and 3) computing fuzzy truth values (Algorithm 4). Initially, each input neuron is assigned an initial fuzzy truth value. When the system halts, the system’s outputs are fuzzy truth values in output neurons. In the following, we explain the basic ideas behind the three components. First Algorithm 2 builds the immediately backward rule-incidence table IRIT according to Π. For each proposition neuron σpk in Π, the algorithm will generate its immediately backward rule-incidence set IBRIS(σpk)and determine the corresponding rule neuron σri according to syn. Thus, (σpk,IBRIS(σpk),σ ri)is composed of a tuple of IRIT. Second, Algorithm 3 is used to generate a fuzzy “⊕-OR” tree of Πbased on the built IRIT. This algorithm starts from output neurons and then, creates each node of fuzzy “⊕-OR” tree according to backward connection relationship of proposition neurons. Each created node has the structure (σpk,IBRIS(σpk),−), where the mark “−” denotes that the fuzzy truth value of the proposition neuron is unknown. In addition to the sides of first level in the tree, other sides are labeled by the certainty factors associated with fuzzy production rules. Finally, Algorithm 4 computes the fuzzy truth value of each nonterminal node of the fuzzy “⊕- OR” tree. Here, fuzzy truth values of terminal nodes, which are associated with input neurons of Π, are known. Starting from terminal nodes, fuzzy truth values of all nonterminal nodes are backward computed on the basis of step 10 or step 12 of the algorithm. The weighted fuzzy backward reasoning algorithm and its three component algorithms are listed in Tables II–V (Algorithms 1–4), respectively. In the following, we briefly discuss the computational complexities and convergence of the aforementioned algorithms. First, Algorithm 2 contains triple loop (m,n, and mtimes, respectively); therefore, its time complexity is O(m2n), and space complexity is O(m2). By analyzing Algorithm3,wecanconclude that its time complexityis O(m2), and space complexity is O(m2). Similarly, time complexity and space complexity of Algorithm 4 are O(m2)and O(m2),respectively. Therefore, the time complexity of Algorithm 1 is O(m2n), while its space complexity is O(m2). Finally, we analyze the convergence of these algorithms. From the descriptions of these algorithms, we know that the roles of Algorithms 2 and 3 are to construct a table IRIT and a tree T, respectively. Therefore, the convergence of the proposed weighted fuzzy reasoning algorithm mainly depends on the convergence of Algorithm 4. Let lbe the largest of the numbers of proposition neurons in all paths of Πfrom input neurons to output neurons. We easily conclude from Algorithm 4 that the algorithm can deduce the TABLE II ALGORITHM 1: WEIGHTED FUZZY BACKWARD REASONING ALGORITHM TABLE III ALGORITHM 2: IRIT BUILDING ALGORITHM values of all unknown proposition neurons at step l, i.e., the algorithm will be converged at step l. In order to clearly understand the algorithms described previously, we use two examples to illustrate the weighted fuzzy backward reasoning process. For Example 1 (Π0), Table I gives the immediate rule-incidence table of its all proposition neurons. By the fuzzy “⊕-OR” tree generating algorithm, a fuzzy “⊕-OR” tree of Π0is generated, as shown in Fig. 5. Assume that the truth value of proposition p1associated with input proposition neuron σp1is 0.8. By performing the fuzzy truth value evaluating algorithm, the truth values of output proposition neurons in Π0are obtained, as shown in Fig. 5, from which it can be clearly seen that the truth value of output proposition neuron σp5is 0.63. Example 2: Let p1,p2,p3,p4,p5,p6,p7,p8, and p9be nine propositions. Assume the knowledge base of a rule-based system contains the following weighted fuzzy production rules. R1:IFp1THEN p5(CF =γ1), ω1. R2:IFp2AND p3THEN p6(CF =γ2), ω2,ω31. R3:IFp3AND p4THEN p7(CF =γ3), ω32,ω4. R4:IFp5AND p6THEN p8(CF =γ4), ω5,ω6. R5:IFp7THEN p9(CF =γ5), ω7. Here, true values, certainty factors, and weights are extended to use triangular fuzzy numbers. Assume the certainty factors γ1,γ 2,γ 3,γ 4, and γ5are (0.80,0.90,1.0),(0.70,0.80,0.90), TABLE IV ALGORITHM 3: FUZZY “⊕-OR” TREE GENERATING ALGORITHM (0.75,0.85,0.95),(0.85,0.95,1.0),and (0.80,0.90,1.0),respectively. Let ω1=(1.0,1.0,1.0),ω 2=(0.85,0.95,1.0),ω 31 =(0.70, 0.80,0.90),ω 32 =(0.85,0.95,1.0),ω 4=(0.75,0.85,0.95), ω5=0.85,0.95,1.0),ω 6=(0.75,0.85,0.95),and ω7=(1.0, 1.0,1.0). The weighted fuzzy production rules can be modeled by using the following WFSN P systems Π5, as shown in Fig. 6: Π5=({a},{σp1,σ p2,σ p3,σ p4,σ p5,σ p6,σ p7,σ p8,σ p9}, {σr1,σ r2,σ r3,σ r4,σ r5},syn,IN,OUT), where 1) σp1,σ p2,σ p3,σ p4,σ p5,σ p6,σ p7,σ p8, and σp9proposition neurons; 2) σr1,σ r2,σ r3,σ r4, and σr5rule neurons. Here, ν1= ω1=(1.0,1.0,1.0),ν2=ω2⊕ω31 =(1.55,1.75,1.90), TABLE V ALGORITHM 4: FUZZY TRUTH VALUE COMPUTING ALGORITHM Fig. 5. Generated fuzzy “⊕-OR” tree of Π0and computation of the fuzzy truth values of the fuzzy “⊕-OR” tree of Π0. Fig. 6. Example 2 modeled by WFSN P systems Π5. TABLE VI IMMEDIATE RULE-INCIDENCE TABLE OF ALL PROPOSITION NEURONS IN EXAMPLE 2 Fig. 7. Generated fuzzy “⊕-OR” tree of Π5and computation of the fuzzy truth values of the fuzzy “⊕-OR” tree of Π5. ν3=ω32 ⊕ω4=(1.6,1.8,1.95),ν4=ω5⊕ω6=(1.6, 1.8,1.95), and ν5=ω7=(1.0,1.0,1.0); 3) syn={(σp1,σ r1),(σp2,σ r2),(σp3,σ r2),(σp3,σ r3),(σp4, σr3),(σp5,σ r4),(σp6,σ r4),(σp7,σ r5),(σr1,σ p5),(σr2, σp6),(σr3,σ p7),(σr4,σ p8),(σr5,σ p9)}; 4) IN ={σp1,σ p2,σ p3,σ p4}, OUT ={σp8,σ p9}. For Example 2 (Π5), Table VI gives the immediate ruleincidence table of all its proposition neurons. By the fuzzy “⊕-OR” tree generating algorithm, a fuzzy “⊕-OR” tree of Π5is generated, as shown in Fig. 7. Assume that the truth values of propositions p1,p 2,p 3, and p4associated with input proposition neurons σp1,σ p2,σ p3, and σp4 are (0.80,0.90,1.0),(0.70,0.80,0.90),(0.85,0.95,1.0), and (0.75,0.85,0.95), respectively. By performing the fuzzy truth value computing algorithm, the truth values of output proposition neurons in Π5are obtained, as shown in Fig. 7, from which it can be easily seen that the fuzzy truth values of output proposition neurons σp8and σp9are fuzzy numbers (0.381,0.714,1.246)and (0.395,0.691,1.130).