Biomedical Engineering Reference
In-Depth Information
Figure 3. Computing a Boolean function of three variables
Point (ii) was proved in (Ionescu et al., 2006)
also for the accepting case, and then the systems
used can be required to be deterministic (at most
one rule can be applied in each neuron in each
step of the computation). In turn, universality
results were proved in (Ionescu et al., 2007) and
(Cavaliere et al., 2007) also for the exhaustive
and for the non-synchronized modes of using the
rules, respectively, but only for extended rules.
The universality of standard systems remains
open
for these cases.
Let us now pass to mentioning some results
about languages generated by SN P systems,
starting with the restricted case of binary strings,
(Chen et al., 2007). We denote by
L
(Π) the set of
strings over the alphabet
B
= {0, 1} describing the
spike trains associated with halting computations
in Π; then, we denote by
LSNP
m
(
rule
k
, cons
p
, forg
q
)
the family of languages
L
(Π), generated by SN P
systems Π with the complexity bounded by the
parameters
m, k, p, q
as specified above. When
using only systems with at most
s
spikes in their
neurons (finite), we write
LSNP
m
(
rule
k
, cons
p
,
forg
q
,
bound
s
) for the corresponding family. As
usual, a parameter
m, k, p, q, s
is replaced with *
if it is not bounded.
Theorem 2
(i)
There are finite languages (for instance,
{0
k
,10
j
}
, for any k ≥
1
, j ≥
0
) which cannot be
generated by any SN P system, but for any fi-
nite language L in B
+
, the language L
{1}
is in
LSNP
1
(rule
*
, cons
*
, forg
0
, bound
*
), and if L =
{
x
1
,
x
2
,..., x
n
}
, then the language
{0
i+3
x
i
| 1 ≤
i ≤ n
}
is
in LSNP
*
(rule
*
, cons
1
, forg
0
, bound
*
).
Search WWH ::
Custom Search