Biomedical Engineering Reference
In-Depth Information
a regular language, while the former paper shows
how length preserving morphisms (codings) can be
computed; the problem remains
open
for arbitrary
morphisms, Kleene *, inverse morphisms.
uses one of these rules and sends the produced
spikes to a collecting neuron which spikes if and
only if it receives in total
S
spikes. The system
is constructed in a semi-uniform way, i.e., start-
ing from the instance to solve. Moreover, with
respect to the size of the problem representation,
the system needs an exponential number of spikes
to initialize.
These drawbacks are removed in (Leporati
et al., 2007b). First, a module is provided which
encodes the input in binary (and this is done in
polynomial time). However, a new way to use the
rules is needed in this phase, namely the maxi-
mally parallel use of rules in each neuron (it is
also proved in (Leporati et al., 2007b) that without
the maximal parallelism this encoding cannot be
done in polynomial time). Then, an SN P system
is constructed,
in a uniform way
, for solving the
Subset Sum problem, also using the idea from
(Leporati et al., 2007a). Therefore, the obtained
system contains both neurons which work in a
deterministic way and neurons which work in a
non-deterministic way, as well as neurons using
the rules in the sequential way and neurons using
the rules in the maximally parallel way. Improv-
ing in unifying the types of neurons from these
points of view is a research topic, and progresses
are expected in this active area of research.
Computation Efficiency
Membrane computing is much investigated as a
framework for devising polynomial solutions to
computationally hard problems (typically,
NP
-
complete problems). So far, only a few results of
this type are known for SN P systems - and they
are briefly mentioned here.
A first interesting result is reported in (Chen
et al., 2006c): SAT can be decided in constant
time by using an arbitrarily large pre-computed
SN P system, of a very regular shape (as synapse
graph) and with empty neurons, after plugging the
instance of size (
n, m
) (
n
variables and
m
clauses) of
the problem into the system, by introducing a poly-
nomial number of spikes in (polynomially many)
specified neurons. This way of solving a problem,
by making use of a pre-computed resource given
for free, on the one hand, resembles the supposed
fact that only part of the brain neurons are active
(involved in “computations”) at each time, on the
other hand, is not very common in computability
and request further research efforts. What kind
of pre-computed resource is allowed, so that no
“cheating” is possible? How the given resources
should be activated? Define and study complexity
classes for this framework.
A more traditional investigation is carried
in (Leporati et al., 2007a) and (Leporati et al.,
2007b). In the first paper, it is proved that the
Subset Sum problem can be decided in constant
time by an extended SN P system working in
a non-deterministic manner. (The Subset Sum
problem asks whether, for given integers
V
= {
v
1
,
v
2
,...,
v
n
} and
S
there is a subset
B
of
V
such that
the sum of the integers in
B
equal
S.
The problem
is known to be
NP
-complete.) The idea is simple:
rules of the forms
a
vi
→ λ,
a
vi
→
a
vi
; 0 are placed
in
n
neurons; non-deterministically, each neuron
FUTURE TRENDS
The theory of spiking neural P systems is rather
young, so many research topics wait to be ad-
dressed in this area. Among them, we mention
here only some important ones: enlarge the
model with further biological facts (for instance,
including the astrocytes, which were already
recently considered); explore in more details the
complexity issues, which are related both to the
(supposed) brain functioning and the possible
applications of SN P systems; link this area to
the traditional neural computing, bringing to
the SN P systems framework such questions
Search WWH ::
Custom Search