Spiking Neural P Systems - Advancing Artificial Intelligence Through Biological Process Applications - page 68

ated when a spike enters the neuron σ (iii) . This
spike causes neuron σ (iii) to immediately send a
spike to the neurons σ li1 , σ (iii) , and σ r . If register
r is not empty, then the rule a ( aaa ) + / a 3 → a ;0
will be applied and the spike emitted will cause
neurons σ li3 , σ li5 , and finally neuron σ lj, to spike.
(In this process, neuron σ li4 has two spikes added
during one step and it cannot spike.) If register
r is empty, hence neuron σ r contains only the
spike received from σ li1 , then the rule a → a ;1
is applied and the subsequent spikes will cause
neurons σ li4 , σ li6 , and finally neuron σ lk, to spike.
(In this process, neuron σ li3 has two spikes added
during one step and does not spike.) After the
computation of the entire module is complete,
each neuron is left with either zero spikes or an
even number of spikes, allowing the module to
be run again in a correct way.
The third example deals with an SN P system
used as a transducer, and it illustrates the follow-
ing result from (Păun et al., 2006b): Any function
f : {0,1} k → {0,1} can be computed by an SN P
system with k input neurons (also using further
2 k + 4 neurons, one being the output one).
The idea of the proof of this result is sug-
gested in Figure 3, where a system is presented
which computes the function f : {0, 1} 3 → {0, 1}
defined by

Computational Power

There are several parameters describing the com-
plexity of an SN P system: number of neurons,
number of rules, number of spikes consumed,
produced, or forgotten by a rule, etc. Here we
consider only some of them and we denote by
N 2 SNP m ( rule k , cons p , forg q ) the family of all sets
N 2 (Π) computed as specified in a previous sec-
tion by standard SN P systems with at most m ≥ 1
neurons, using at most k ≥ 1 rules in each neuron,
with all spiking rules E/a r → a ; t having r ≤ p , and
all forgetting rules a s →λ having s ≤ q . When any
of the parameters m, k, p, q is not bounded, it is
replaced with *. When we work only with SN P
systems whose neurons contain at most s spikes
at any step of a computation (finite systems), then
we add the parameter bound s after forg q . (Corre-
sponding families are defined for other definitions
of the result of a computation, as well as for the
accepting case, but the results are quite similar,
hence we do not give details here.)
By NFIN, NREG, NRE we denote the fami-
lies of finite, semilinear, and Turing computable
sets of (positive) natural numbers (number 0
is ignored); they correspond to the length sets
of finite, regular, and recursively enumerable
languages, whose families are denoted by FIN,
REG, RE . We also invoke below the family of
recursive languages, REC (those languages with
a decidable membership).
The following results were proved in (Io-
nescu et al., 2006) and extended in (Păun et al.,
2006a) to other ways of defining the result of a
computation.

f ( b 1 , b 2 , b 3 ) = 1 if and only if b 1 + b 2 + b 3 ≠ 2.

The three input neurons, with labels in 1 , in 2 ,
in 3 , are continuously fed with bits b 1 , b 2 , b 3 , and
the output neuron will provide, with a delay of
3 steps, the value of f ( b 1 , b 2 , b 3 ). The details are
left to the reader.

Theorem 1
(iii) NFIN = N 2 SNP 1 ( rule * , cons 1 , forg 0 ) =
N 2 SNP 2 ( rule * , cons * , forg * ).

SOME RESULTS

Mainly the power of SN P systems was investi-
gated so far, but also their usefulness for solving
computationally hard problems. We start by briefly
presenting some results of the first type.

(iii) N 2 SNP * ( rule k , cons p , forgq 0 ) = NRE, for all k
≥ 2, p ≥ 3, q ≥ 3.

(iii) NSLIN = N 2 SNP * ( rule k , cons p , forg q , bound s ),
for all k ≥ 3, p ≥ 3, q ≥ 3, s ≥ 3.