Biomedical Engineering Reference
In-Depth Information
(iii)
The family of languages generated by finite
SN P systems is strictly included in the family of
regular languages over the binary alphabet, but
for any regular language L over an alphabet V
there is a finite SN P system
Π
and a morphism
h : V
*
→ B
*
such that L = h
-1
(L(Π)).
The next counterparts of the results from
Theorem 2 were proved in (Chen et al., 2006a).
Theorem 3
(iii)
FIN = LSN
e
P
1
(rule
*
, cons
*
, prod
*
) and this result
is sharp, as LSN
e
P
2
(rule
2
, cons
2
, prod
2
) contains
infinite languages.
(iii)
LSNP
*
(rule
*
, cons
*
, forg
*
) is included in REC,
but for every alphabet V =
{
a
1
, a
2
,..., a
k
}
there
are two symbols b, c not in V, a morphism h
1
: (V
+
{
b,c
}
)
*
→ B
*
, and a projection h
2
: (V +
{
b,c
}
)
*
→ V
*
such that for each language L over V, L
in RE, there is an SN P system Π such that L =
h
2
(h
1
-1
(L(Π))).
(iii)
LSN
e
P
2
(rule
*
, cons
*
, prod
*
) is included in
REG and REG is included in LSN
e
P
3
(rule
*
, cons
*
,
prod
*
); the second inclusion is proper, because
LSN
e
P
3
(rule
3
, cons
4
, prod
2
) contains non-regular
languages; moreover, LSN
e
P
3
(rule
3
, cons
6
, prod
4
)
contains non-semilinear languages.
These results show that the language generat-
ing power of SN P systems is rather eccentric; on
the one hand, finite languages (like {0, 1}) cannot
be generated, on the other hand, we can represent
any RE language as the direct morphic image of
an inverse morphic image of a language gener-
ated in this way. This eccentricity is due mainly
to the restricted way of generating strings, with
one symbol added in each computation step.
This restriction does not appear in the case of
extended spiking rules. In this case, a language
can be generated by associating the symbol
b
i
with a step when the output neuron sends out
i
spikes, with an important decision to take in the
case
i
= 0: we can either consider
b
0
as a separate
symbol, or we can assume that emitting 0 spikes
means inserting λ in the generated string. Thus,
we both obtain strings over arbitrary alphabets, not
only over the binary one, and, in the case where
we ignore the steps when no spike is emitted, a
considerable freedom is obtained in the way the
computation proceeds. This latter variant (with
λ associated with steps when no spike exits the
system) is considered below.
We denote by
LSN
e
P
m
(rule
k
, cons
p
, prod
q
)
the
family of languages
L
(Π), generated by SN P sys-
tems Π using extended rules, with the parameters
m, k, p, q
as above.
(iii)
RE = LSN
e
P
*
(rule
*
, cons
*
, prod
*
).
It is an
open problem
to find characterizations
or representations in this setup for families of
languages in the Chomsky hierarchy different
from
FIN, REG, RE
.
We close this section by mentioning the results
from (Păun and Păun, 2007):
Theorem 4
There is a universal computing SN P system
with
(iii)
standard rules and 84 neurons and with
(iii)
extended rules and 49 neurons, and there
is a universal SN P system used as a generator
of sets of numbers with
(iii)
standard rules and
76 neurons and with
(iv)
extended rules and 50
neurons.
These values can probably be improved (but
the feeling is that this improvement cannot be
too large).
Tool-kits for handling strings or infinite se-
quences, on the binary or on the arbitrary alphabet,
are provided in (Păun et al., 2006b) and (Chen et
al., 2006c). For instance, in this latter paper one
gives constructions of SN P systems for comput-
ing the union and concatenation of two languages
generated by SN P systems, the intersection with
Search WWH ::
Custom Search