# Sequential Spiking Neural P Systems with Local Scheduled Synapses without Delay

Authors: Alia Bibi; Fei Xu; Henry N. Adorna; Francis George C. Cabarle
Journal: Complexity
 (2019)

---

## Abstract

Spiking neural P systems with scheduled synapses are a class of distributed and parallel computational models motivated by the structural dynamism of biological synapses by incorporating ideas from nonstatic (i.e., dynamic) graphs and networks. In this work, we consider the family of spiking neural P systems with scheduled synapses working in the sequential mode: at each step the neuron(s) with the maximum/minimum number of spikes among the neurons that can spike will fire. The computational power of spiking neural P systems with scheduled synapses working in the sequential mode is investigated. Specifically, the universality (Turing equivalence) of such systems is obtained.


---

## Body

## 1. Introduction

Spiking neural P systems (abbreviated as SN P systems) were first introduced in [1] as a class of parallel and distributed neural-like computational models, which are inspired from the fact that spiking neurons communicate with each other through electrical impulses. An SN P system could be viewed as a directed graph with nodes consisting of a number of computing units called neurons and the arcs representing the synapses. Each neuron contains copies of a single object type called the spike and a set of spiking rules that produces one or more spikes from the source neuron to every neuron connected by a synapse and forgetting rules that removes spikes from the neuron.Many efforts have been made to investigate the theoretical and practical aspects of SN P systems, since the computational model was introduced. The computational power of SN P systems was investigated as different computing devices, e.g., number generating/accepting devices [1], language generators [2, 3], and function computing devices [4]. By abstracting computing ideas from the human brain and biological neurons, many variants of SN P systems have been introduced, such as axon P systems [5], SN P systems with rules on synapses [6–8], SN P systems with weights [9], SN P systems with neuron division and budding [10], SN P systems with structural plasticity [11], cell-like SN P systems [12], fuzzy reasoning SN P systems [13–16], probabilistic SN P systems [17], SN P systems with multiple channels [18], SN P systems with scheduled synapses (SSN P systems for short) [19], coupled neural P systems [20], dynamic threshold neural P systems [21], SN P systems with colored spikes [22], and SN P systems simulators [23, 24].Although biological processes in living organisms happen in parallel, they are not synchronized by a universal clock as assumed in SN P systems. Introduced in [25], sequential SN P systems are a class of computing devices that plays a role of a bridge between spiking neural networks and membrane computing [26]. Two types of sequentiality are considered in sequential SN P systems: the general sequentiality [25] and sequentiality induced by the spike(s) number [27–29]. The first case is the classical pure-sequential model of its family. The fact behind the pure-sequentiality is that these systems are completely (purely) sequential according to neurons; at each time unit, one and only one neuron among all active neurons is nondeterministically chosen to fire. The second case is based on the first one, where the sequentiality is induced on the basis of number of spikes (either maximum or minimum) present in active neurons; on the basis of spikes number we have further two types: maximal sequential SN P systems and minimal sequential SN P systems.In this work, we consider SN P systems with scheduled synapses (SSN P systems) which is inspired and motivated by the structural dynamism of biological synapses, while incorporating ideas from nonstatic (i.e., dynamic) graphs and networks from mathematics. Synapses in SSN P systems are only available at a specific schedule or duration. The schedules are of two types: local and global scheduling, named after a specified reference neurons: local reference neurons and global reference neurons. In the first case synapses are called local scheduled synapses, in which synapses are scheduled locally with respect to their local reference neurons; there can be multiple reference neurons within a system; however each synapse is associated with exactly one reference neuron. In the second case synapses are called global-scheduled synapses, in which synapses are scheduled globally with respect to a single-shared global reference neuron. In particular, we consider SN P systems with local scheduled synapses working in the sequential mode without delay (SSSN P systems, for short), where the sequentiality induced by the maximum/minimum (max/min, for short) spike(s) number is introduced. The computational power of SSSN P systems working in strong sequentiality or pseudosequentiality strategies is investigated. Specifically, SSSN P systems working in the max/min-sequentiality (resp., max/min-pseudosequentiality) strategy are proved to be Turing universal.The paper is organized as follows: Section2 provides definitions of some concepts necessary for the understanding of the paper. We introduce in Section 3 our variant of SN P systems, namely, sequential SN P systems with local scheduled synapses working in max/min-sequential strategy without delay (SSSN P systems). We present our universality results in Section 4 and finally provide final remarks in Section 5.


## 2. Preliminaries

In this section, various notions and notations from formal language theory and computability theory that we shall use in the remainder of the paper are explained. The reader is also assumed to have a basic familiarity with membrane computing. Both the basics of membrane computing and its formal language and computability theory prerequisites are covered in sufficient detail in [30] and the handbook in [31].We denote byΣ a nonempty finite set of symbols called alphabet, and Σ
∗ is known as the set of all strings of symbols generated from Σ, including λ, the empty string. The set of nonempty string over Σ
∗ is denoted by Σ
+
=
Σ
∗
-
{
λ
}. Each L subset of Σ
∗ is called a language over Σ. A language L is called λ-free, if it does not contain empty string (thus is a subset of Σ
+). A set of collection of languages is called a family of languages. We define inductively regular expressions over an alphabet Σ and the language they describe as follows: λ and every symbol a
∈
Σ are regular expressions. If E
1 and E
2 are regular expressions, then E
1
+
E
2, E
1
E
2, and E
1
∗ are also regular expressions. We denote by L
(
E
1
) the language described by the regular expression E
1. In particular, we have L
(
λ
)
=
{
λ
}, L
(
a
)
=
{
a
}, L
(
E
1
+
E
2
)
=
L
(
E
1
)
∪
L
(
E
2
), L
(
E
1
E
2
)
=
L
(
E
1
)
L
(
E
2
), and L
(
E
1
∗
)
=
L
(
E
1
)
∗.Our universality results are proved by allowing our proposed model to simulate a well-known universal computing model called register machine [1, 32].A register machineM is a construct of the form: M
=
(
m
,
H
,
l
0
,
l
h
,
I
), where(i)
m is the number of registers,
(ii)
H is the set of instruction labels,
(iii)
l
0 is the start label (which labels an instruction ADD),
(iv)
l
h is the label halt (which is assigned to instruction H
A
L
T),
(v)
I is the set of instructions.A register machineM could accept or generate a number n. In this work, we use a register machine M that generates numbers. We denote the set of all numbers computed/generated by M as N
(
M
). Since register machine computes all sets of numbers that are Turing computable, then we have N
(
M
)
=
N
R
E, where N
R
E denotes the family of languages recognized by Turing machine.


## 3. Sequential SN P Systems with Local Scheduled Synapses Working in Max/Min-Sequential Strategy without Delay

We give here the definition of sequential SN P systems with local scheduled synapses without delay.Definition 1.
A sequential SN P system with local scheduled synapses without delay, SSSN P system for short, of degreem
≥
1 is a construct of the form
Π
=
(
Σ
,
σ
1
,
σ
2
,
…
,
σ
m
,
r
e
f
,
s
y
n
,
S
,
o
u
t
) where (a)
Σ
=
{
a
} is the singleton alphabet (a is called spike);
(b)
σ
1
,
σ
2
,
…
,
σ
m are neurons of the form σ
i
=
(
n
i
,
R
i
), 1
≤
i
≤
m where
(1)
n
i
≥
0 is the initial number of spikes contained in σ
i;
(2)
R
i is a finite set of rules of the form
(i)
E
/
a
c
→
a
p, where E is a regular expression over a;
(ii)
a
s
→
λ for some s
≥
1, with restriction that a
s
∉
L
(
E
) for any rule E
/
a
c
→
a
p of type (i) from R
i, where E is a regular expression over a and c
≥
1, p
≥
0, and c
≥
p;
(c)
s
y
n
⊂
{
1,2
,
…
,
m
}
×
{
1,2
,
…
,
m
}
×
(
T
∪
{
O
N
}
) is the set of synapses among neurons, where T is the set of schedules of the form (q
,
r
∣
q
,
r
≥
0
,
q
<
r), no σ
i has a synapse to itself, and each synapse has exactly one schedule;
(d)
S
⊂
P
(
s
y
n
)
×
P
(
r
e
f
) is the set of synapse references, P
(
x
) is the power set of the set x, and r
e
f
⊆
{
1,2
,
…
,
m
} is the set of reference neurons. For any two pairs (
s
1
,
r
1
), (
s
2
,
r
2
)
∈
S, we have s
1
∩
s
2
=
∅ and r
1
∩
r
2
=
∅;
(e)
o
u
t is the label for output neurons.The semantics of spiking rule application is as follows: Letσ
i be a neuron containing b spikes and a rule E
/
a
c
→
a
p
∈
R
i. If b
≥
c and a
b
∈
L
(
E
), then E
/
a
c
→
a
p
∈
R
i can be applied. With this rule application σ
i will consume c spikes to send p spike(s) to its adjacent neurons, then it will have b
-
c spikes remaining. If p
=
1 then rule E
/
a
c
→
a
p
∈
R
i serves as a standard rule and otherwise as an extended rule. In general, a neuron can have at least two spiking rules with regular expressions E
1 and E
2 such that L
(
E
1
)
∩
L
(
E
2
)
≠
∅. In this case, if the regular expression is satisfied, then we nondeterministically choose one of the rules to be applied. Additionally, our system is sequential and synchronized so that at each step, among all the active neurons, the one with maximum/minimum number of spikes can apply its rule. Rule application is sequential both at the neurons and at system level. This means at each time schedule exactly single rule can be applied by a spiking neuron and similarly one and only one neuron (holding maximum/minimum number of spikes) can fire among all the active neurons. Thus all the neurons apply their rules at maximum/minimum and in sequence. As a convention if a rule E
/
a
c
→
a
p has E
=
a
c then we write it as a
c
→
a
p, instead. Moreover synapse from the output neuron labeled with O
N is always assumed available.The semantics of synapse schedule is as follows: the synapses are scheduled according to the activation of the reference neuron. A scheduled synapse takes effect immediately upon activation of its reference neuron. The reference neuron is indicated with the symbol “•”, (e.g., σ
i
•). If at step t, a reference neuron σ
i
• becomes activated with a synapse scheduled with [
q
,
r
), then it means that synapse is active only from the step “t
+
q” to “t
+
r”. If at some step a rule is applied by a neuron σ
i, but there is no respective scheduled synapse at that time, then that spike gets wasted as no adjacent neuron will receive it.The semantics of sequentiality either maximum/minimum is as follows: if at any step there are more than one active neurons (neurons with enabled rules are called active), then only the neuron(s) containing the maximum/minimum number of spikes (among the currently active neurons) will be able to fire. If there is a tie among two or more active neurons (all holding equal number of spikes), then there are two different strategies considered in SSSN P systems: strong sequentiality and pseudosequentiality. In the first strategy one and only one active neuron is nondeterministically chosen among all the tied neurons to fire, while in the second strategy all the tied neurons fire simultaneously; let us assume that, in max-sequential case, at a given step there are four active neurons:x
1, x
2, x
3, and x
4 with spikes stored 4, 5, 5, and 1, respectively; it is obvious that there is a tie between neurons x
2 and x
3; so in strong max-sequential case either neuron x
2 or x
3 will be nondeterministically chosen to fire, but in max-pseudosequential case both neurons will fire simultaneously.A configuration of the system in a given step is the distribution of spikes among neurons and the status of each neuron, whether closed or open. The initial configuration is given byn
i of each neuron σ
i and all neurons are open.Starting from the fixed initial configuration (distribution of spikes among neurons) and applying the rules in synchronized manner (a global clock is assumed), the system gets evolved. Applying the rules according to the above description, transitions among configuration can be defined.Applying the rules in this way, the system passes from one configuration to another configuration. Such a step is known as transition. Given two configurationsC
1, C
2 of Π, the direct transition between these two configurations is represented by C
1
⇒
C
2. While the reflexive and transitive closure of the relation ⇒ is represented by ⇒
∗. A transition is sequential provided that, among all the candidate neurons, one holding maximum/minimum number of spikes must apply the rule.A computation is the sequence of transitions, starting from the initial configuration to the final configuration. A computation is said to be successful or a halting computation, if it reaches a configuration where no further rule(s) can be applied. Moreover all the neurons must be restored to their valid states.There are various ways to define the result or output of the computation, but in this work we use the following type: we consider only the first two spikes fired or produced by the output neuron at stepst
1 and t
2. The number computed by SSSN P systems in max-sequential case is the difference between first two spikes minus one, i.e., t
2
-
t
1
-
1, while in min-sequential case it is the difference between first two spikes minus two, i.e., t
2
-
t
1
-
2.We denote withN
α
(
Π
β
γ
) the family of all sets of numbers generated by SN P systems working in sequential mode with local scheduled synapses and without delay. Here α
∈
{
2
,
g
e
n
} means that the number generated is encoded by the first two spikes of the output neuron; g
e
n means that system works in generative mode; β
=
l
o
c means only local scheduled synapses is used; γ
∈
{
m
a
x
/
m
i
n
,
m
a
x
p
/
m
i
n
p
} indicates the max/min-sequentiality and max/min-pseudosequentiality modes of the systems; e means extended rules. Moreover we will take into account only halting computation.We follow the conventional practice by ignoring the number zero, when comparing the power of two number generating devices, as empty string is ignored in formal languages and automata theory while comparing two language generating devices.


## 4. Results on Computational Power

In what follows, we start describing our results for SSSN P systems with local schedules and without delays by giving theorems for both sequential strategies: based on max/min-sequentiality and on max/min-pseudosequentiality. Due to the scheduled synapses our systems are deterministic at the system level; nondeterminism is shifted to the level of neurons in both sequential strategies: strong sequential and pseudosequential. By simulating register machines we prove universality for both strategies.


### 4.1. Max-Sequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the max-sequential strategy orS
m
a
x
S
S
N
P
l
o
c systems in short. Here the superscript m
a
x stands for max-sequential and the subscript l
o
c means local scheduling. We note that for this section we make use of extended rules which are spiking rules where p
≥
2. In our results we use parameters, similar to [19] and other works on universality. Parameters r
u
l
e
i
,
f
o
r
g
j
,
c
o
n
s
k specify at most i
≥
1 rules in each neuron, forgetting at most j
≥
1 spikes and consuming at most k
≥
1 spikes, respectively.Theorem 2.
N
2
,
g
e
n
S
m
a
x
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem2, we will simulate a register machine M with an S
m
a
x
S
S
N
P
l
o
c system Π. Prior to construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. The local reference neuron is labeled with “•”. If the content of r is the number n, then spikes stored in its corresponding σ
r are 2
n
+
2. If M applies some instruction l
i such that some operation, i.e., ADD, SUB, or HALT, is performed by M this means a neuron σ
l
i begins to simulate the operation. We provide modules ADD, SUB, and FIN in order to simulate all three types of instructions of M.
Module ADD. In Figure 1 we give the graphical description of the module simulating a rule of the form l
1
:
(
A
D
D
(
r
)
,
l
2
,
l
3
).
The module functions are as follows: here the reference neuron isl
1, so it is labeled with •, i.e., l
1
•. The simulation starts from the reference neuron l
1
•. Once l
1
• applies its rule, it sends one spike to each of neurons x
1 and x
2 at schedule [
0,1
). In step 2, neuron x
1 is active with two spikes. Neuron x
1 applies its extended rule at schedule [
1,2
) to send two spikes to each of neurons x
2 and r. Neuron r now has two new spikes added to its previous spikes. If the number of spikes in neuron r is even then neuron r does not apply any rule. It is worth noting that we use here an extended rule instead of a standard rule as it is a strong sequential case, which means at most one neuron can fire at any step. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on which rule of neuron x
2 is applied. We have the following two cases depending on which rule is applied by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes all 3 spikes of neuron x
2 and sends one spike to each of neurons x
1 and x
3. In this way, the single spike of neuron x
1 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
2 in order to begin simulating l
2 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes one spike and sends one spike to each of neurons x
1 and x
3. In this way, the single spike of neuron x
1 is restored. At schedule [
3,4
) both neurons x
2 and x
3 can apply their rules, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has only one spike. Hence at [
3,4
) rule a
2
→
a of neuron x
2 is applied. At [
4,5
) neuron x
4 applies its rule to consume one spike and send one spike to each of neurons x
3 and l
3. At [
5,6
), neuron x
3 has the most spikes so it applies its forgetting rule. At [
6,7
) neuron l
3 becomes active to begin simulating l
3 of M.
The simulation of ADD is complete as the number of spikes in neuronr increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. We note that neuron r remains inactive as long as its content remains even. Hence, when simulating ADD neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. In Figure 2 we give the graphical description of the module SUB simulating a rule of the form l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
). The module functions are as follows: at schedule [
0,1
), the reference neuron l
1
• is activated and fires sending one spike to each of neurons r
,
s
1, and c
i
1. The SUB module always has two cases depending on the value n in register r: either n
=
0 (when register r is empty) or n
≥
1 (when register r is nonempty). We explain both the cases separately beginning at schedule [
1,2
).
Case I. When n
=
0 in register r, then neuron r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 and c
i
1 have 2 and 4 spikes, respectively. Due to max-sequentiality, c
i
1 is the activated neuron so it fires consuming one spike and sending a spike at [
1,2
). Due to the spiking of neuron c
i
1, neuron c
i
2 now has 4 spikes. Neuron c
i
2 is activated and it fires one spike each to s
1 and c
i
3 at [
2,3
). Neurons s
1 and c
i
3 now have 3 and 5 spikes each, respectively. Neuron c
i
3 is activated so it consumes one spike and sends a spike to neuron s
1 at [
3,4
). Now neuron s
1 has 4 spikes and applies its forgetting rule at [
4,5
). Neuron r is now activated so applying its second rule, it consumes one spike and sends it to neuron s
3 at [
5,6
). At [
6,7
) neuron s
3 fires sending a spike to neurons l
3 and s
1. Neurons r and s
1 now each have their original spikes with 2 and 1 spikes, respectively. Lastly at [
7,8
) neuron l
3 is activated to begin simulating instruction l
3 of M.
Case II. When n
≥
1 in register r, this means neuron r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron r fires sending a spike to neuron s
1 at [
1,2
) and consuming 3 spikes. Hence, neuron r now has 2
n spikes corresponding to subtracting the content of register r by 1. Neuron c
i
1 has the most spikes, so it fires sending a spike to each of neurons s
1 and c
i
3 at [
2,3
). At [
3,4
) neuron c
i
3 has the most spikes so it fires sending a spike to neuron s
1. At [
4,5
) neuron s
1 now has 5 spikes and it fires sending a spike to neuron s
2. At [
5,6
) neuron s
2 fires sending one spike each of neurons s
1 (restoring the single spike of s
1) and l
2. Lastly at [
6,7
) neuron l
2 is activated to simulate the instruction l
2 of M.
In both scenarios the module SUB is restored to its initial configuration after simulating a SUB instruction. Since a registerr in M can be associated with two or more SUB instructions, we must check for interference among several SUB modules. We find that there is no interference due to the semantics of local schedule. Let l
i and l
x be SUB instructions on register r, and let l
i be the instruction to be simulated. Neuron σ
r can have a synapse to neurons s
1 and s
3 in the modules associated with instructions l
i and l
x. Due to the local schedule of synapses, only synapses associated with the simulated instruction l
i are available. Neurons not associated with l
i are not available; hence they do not receive any spikes from σ
r. In this way, no wrong simulations are performed by Π.
Module FIN: Halting the Computation. To complete the computation, the module FIN is depicted in Figure 3. Assume that register machine M has halted; i.e., its instruction l
h has been applied. This means that Π simulates l
h and begins to output the result. Recall that register 1 is never decremented; i.e., it is never associated with S
U
B instruction. This means that σ
1 holds 2
n spikes. At [
0,1
) reference neuron l
h
• fires sending a spike to each of neurons l
h
1 and the output neuron σ
o
u
t. At [
1,2
) neuron l
h
1 fires sending a spike to neuron σ
o
u
t. At [
2,3
) neuron σ
o
u
t fires sending the first spike (out of three spikes) to the environment and to neuron σ
1. At the next step neuron σ
1 is activated since it has 2
n
+
1
≥
3 spikes. For the next n steps neuron σ
1 continues to apply its rule to consume 2 spikes. After n
+
1 steps neuron σ
1 has only one spike so at this step neuron σ
o
u
t spikes sending a spike to the environment for the second and last time. Finally at step n + 2, neuron σ
1 forgets its last spike. The first and second spike of neuron σ
o
u
t were sent out at step t and t
+
n
+
1, respectively. Hence the result of the computation of Π is (
t
+
n
+
1
)
-
t
-
1
=
n, exactly the value in register r when register machine M halts. All parameters for r
u
l
e, f
o
r
g, and c
o
n
s are satisfied, and an extended rule is used in ADD module. This completes the proof.Figure 1
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 2
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).Figure 3
Module FIN.In what follow, we consider max-pseudosequential strategy: a more realistic approach of spiking for neurons in the system: in case of a tie among active neurons, then all the tied neurons will fire simultaneously.


### 4.2. Max-Pseudosequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the max-pseudosequential strategy, abbreviated asS
m
a
x
p
S
S
N
P
l
o
c systems.Theorem 3.
N
2
,
g
e
n
S
m
a
x
p
S
S
N
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem3, we simulate a register machine M with an S
m
a
x
p
S
S
N
P
l
o
c system Π. Prior to the construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. If register r stores the number n, then neuron σ
r has 2
n
+
2 spikes. If some instruction l
i is applied by M this means neuron σ
l
i begins simulating the instruction. In contrast to Theorem 2, in Theorem 3, due to max-pseudosequentiality we do not need extended rules; only standard rules are enough to prove universality.
Module ADD. The template module for the ADD instruction is depicted in Figure 4. The local reference neuron l
1
• fires at schedule [
0,1
) sending one spike to each of neurons x
1, x
2, and x
3. At [
1,2
) there is a tie between neurons x
1 and x
2 (both have equal number of spikes), but due to max-pseudosequentiality, both neurons fire simultaneously and both send one spike each to neurons x
3 and r. In this way neuron σ
r receives two spikes corresponding to an increment of 1 in the stored value in register r. At the next step neuron x
3 must nondeterministically decide which rule to apply, so we have the following two cases.
Case I. When neuron x
3 applies rule a
3
→
a at [
2,3
), one spike is sent to neuron x
4. Neuron x
4 fires sending a spike to neuron l
2 at [
3,4
), which means system Π will simulate the next instruction l
2 of M.
Case II. When neuron x
3 applies its rule a
3
/
a
→
a it consumes one spike, so two spikes remain. Neuron x
4 receives a spike from neuron x
3 but cannot fire since neuron x
3 still has the most spikes. At [
3,4
) neuron x
3 applies a
2
→
a firing and sending a spike to neuron x
5. Again there is a tie between neurons x
4 and x
5 at [
4,5
) but due to max-pseudosequentiality both fires at a single step, sending a spike but only l
3 receives a spike; the spike of x
4 is wasted as there is no synapse from it at schedule [
4,5
). This means system Π is ready to simulate the next instruction l
3 of M.
The simulation of an ADD instruction is correct: contents ofσ
r are increased by two, followed by nondeterministically activating either neuron l
2 or l
3.
Module SUB. To simulate instruction l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
) we have the SUB module in Figure 5. At schedule [
0,1
) the local reference neuron l
1
• fires sending one spike to each of neurons c
i
1, c
i
2, and s
1. At the next step neurons c
i
1, c
i
2, and s
1 have 1, 1, and 2 spikes, respectively. Due to max-pseudosequentiality, both tied neurons c
i
1 and c
i
2 with equal number of spikes fire simultaneously at [
1,2
). Neuron r receives one spike from neuron c
i
1 while neuron s
1 receives two, one each from neurons c
i
1 and c
i
2. At this point neuron σ
r has the following two cases depending on the value of n in register r.
Case I. When n
=
0, this means neuron σ
r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes, the most at [
2,3
) so it applies its forgetting rule. At [
3,4
) neuron r applies its rule consuming and producing one spike, sending the spike to neuron s
3. In this way the spikes in σ
r return to 2
n
+
2 indicating n
=
0 in register r. At [
4,5
) neuron s
3 fires and so Π begins to simulate the next instruction l
3.
Case II. When n
≥
1, this means that neuron σ
r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron r fires at [
2,3
), consuming 3 spikes (to simulate the decrement of n by 1) and sending a spike to neuron s
1. At [
3,4
) neuron s
1 has 5 spikes and fires sending a spike to neuron s
2. At [5,6) neuron s
2 fires send one spike each to neurons s
1 (restoring the single spike of s
1) and l
2. Hence, system Π will simulate the next instruction l
2.
As due to the semantics of local reference neuron, there is no interference with any SUB module. The simulation of the SUB instruction is correct: if registerr is nonempty then spikes in neuron σ
r are decreased by 2 followed by activating neuron l
2; if register r is empty then spikes in neuron σ
r are not decreased and neuron l
3 is activated. It is to be noted that with slight high complexity the SUB module in Figure 2 for max-sequentiality can also be used in M
m
a
x
pSSN P
l
o
c systems.
Module FIN: Halting the Computation. The module FIN in Figure 3 can also be used in M
m
a
x
pSSN P
l
o
c systems to produce the output of Π.
It is clear that all three modules have utilized at most 3 rules in each neuron, consumed at most 5 spikes while forgetting at most 4 spikes. The synapses of each module are synchronized with respect to their related local reference neurons. We also note that no extended rules are needed in max-pseudosequentiality. The parameters of the theorem are satisfied, thus completing the proof.Figure 4
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 5
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).


### 4.3. Min-Sequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the min-sequential strategy orS
m
i
n
S
S
N
P
l
o
c systems in short. Here the superscript m
i
n stands for min-sequential and the subscript l
o
c means local scheduling. We note that, due to min-sequentiality, in ADD module we do not make use of extended rules as compared to Theorem 2. Extended rule is used only in FIN module. In our results we use parameters, similar to [19] and other works on universality. Parameters r
u
l
e
i
,
f
o
r
g
j
,
c
o
n
s
k specify at most i
≥
1 rules in each neuron, forgetting at most j
≥
1 spikes, and consuming at most k
≥
1 spikes, respectively.Theorem 4.
N
2
,
g
e
n
S
m
i
n
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem4, we will simulate a register machine M with an S
m
i
n
S
S
N
P
l
o
c system Π. Prior to construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. The local reference neuron is labeled with “•”. If the content of r is the number n, then spikes stored in its corresponding σ
r are 2
n
+
2. If M applies some instruction l
i such that some operation, i.e., ADD, SUB, or HALT, is performed by M this means a neuron σ
l
i begins to simulate the operation. We provide modules ADD, SUB, and FIN in order to simulate all three types of instructions of M.
Module ADD. In Figure 6 we give the graphical description of the module simulating a rule of the form l
1
:
(
A
D
D
(
r
)
,
l
2
,
l
3
).
The module functions are as follows: the simulation starts from the reference neuronl
1
•
. Once l
1
• applies its rule, it sends one spike to each of neurons x
1, x
2, and r at schedule [
0,1
). It is worth noting that, in order to keep neuron r inactive, its content must be even; adding one spike to the content of register r means that it is active to fire now, but due to min-sequentiality neuron x
1 will fire next at step 2. Neuron x
1 applies its rule at schedule [
1,2
) to send a spike to each of neurons x
2 and r. Neuron r has now one more spike added to its previous spikes. As the number of spikes in neuron r is even now so it will not apply any rule. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on which rule of neuron x
2 is applied. We have the following two cases depending on which rule is applied by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
/
a
2
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes two spikes of neuron x
2 and sends one spike to x
3. In this way, the single spike of neuron x
2 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
3 in order to begin simulating l
3 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes and sends one spike to neuron x
3. At schedule [
3,4
) both neurons x
2 and x
3 are active, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has three spike. Hence at [
3,4
), rule a
2
/
a
→
a of neuron x
2 is applied and one spike is sent to neuron x
4. At [
4,5
) both neurons x
3 and x
4 are active, but only neuron x
3 with less spikes applies its rule; the spike fired by neuron x
3 is not received by any neuron, since neuron x
3 has no synapse at schedule [
4,5
). At [
5,6
), neuron x
4 fires sending a spike to l
2. At [
6,7
) neuron l
2 becomes active to begin simulating l
2 of M.
The simulation of ADD is complete as the number of spikes in neuronr is increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. Since neuron r remains inactive as long as its content remains even. Hence, when simulating ADD neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. In Figure 7 we give the graphical description of the module SUB simulating a rule of the form l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
). The module functions are as follows: At schedule [
0,1
), the reference neuron l
1
• is activated and fires sending one spike to each of neurons r
,
s
1 and c
i
1. Due to min-sequentiality, c
i
1 is the activated neuron so it fires and sends a spike at [
1,2
). Due to the spiking of neuron c
i
1, neurons s
1 and c
i
2 now have 3 and 1 spikes, respectively. Neuron c
i
2 is activated and it fires one spike to s
1 at [
2,3
).
The SUB module always has two cases depending on the valuen in register r: either n
=
0 (when register r is empty) or n
≥
1 (when register r is nonempty). We explain both cases separately beginning at schedule [
3,4
).
Case I. When n
=
0 in register r, then neuron r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes. Neuron r is now activated with less spikes so applying its second rule, it consumes one spike and sends it to neuron s
1 at [
3,4
). At [
4,5
) neuron s
1 fires sending a spike to neuron s
3. At [
5,6
) neuron s
3 fires sending a spike to s
1 and l
3. Neurons r and s
1 now each have their original spikes with 2 and 1 spikes, respectively. Lastly at [
6,7
) neuron l
3 is activated to begin simulating instruction l
3 of M.
Case II. When n
≥
1 in register r, this means neuron r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron s
1 has 4 spikes, the less at [
3,4
) so it applies its forgetting rule. Neuron r fires sending a spike to neuron s
2 at [
4,5
) and consuming 3 spikes. Hence, neuron r now has 2
n spikes corresponding to subtracting the content of register r by 1. At [
5,6
) neuron s
2 fires sending one spike to each of neurons s
1 (restoring the single spike of s
1) and l
2. Lastly at [
6,7
) neuron l
2 is activated to simulate the instruction l
2 of M.
In both scenarios the module SUB is restored to its initial configuration after simulating a SUB instruction. There is no interference in this module due to the semantics of local scheduling.
Module FIN: Halting the Computation. To complete the computation, the module FIN is depicted in Figure 8. Assume that register machine M has halted; i.e., its instruction l
h has been applied. This means that Π simulates l
h and begins to output the result. At [
0,1
) reference neuron l
h
• fires sending a spike to the output neuron σ
o
u
t. At [
1,2
) neuron σ
o
u
t fires sending the first spike (hence t
1) out of three spikes to the environment and to neuron σ
1. At the next step neuron σ
1 is activated since it has 2
n
+
1
≥
3 spikes. For the next n steps neuron σ
1 continues to apply its extended rule to consume and produce 2 spikes. At n
+
1 step, neuron σ
1 has only one spike so by applying second rule neuron σ
1 spikes sending one spike to neuron σ
o
u
t (hence activating it for the second time with odd number of spikes). At n
+
2 step, neuron σ
o
u
t spikes (hence t
2) sending a spike to the environment for the second and last time. The first and second spike of neuron σ
o
u
t were sent out at step t and t
+
n
+
2, respectively. Hence the result of the computation of Π is (
t
+
n
+
2
)
-
t
-
2
=
n, exactly the value in register r when register machine M halts. All parameters for r
u
l
e, f
o
r
g, and c
o
n
s are satisfied, and an extended rule is used in FIN module. This completes the proof.Figure 6
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 7
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).Figure 8
Module FIN.


### 4.4. Min-Pseudosequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the min-pseudosequential strategy, abbreviated asS
m
i
n
p
S
S
N
P
l
o
c systems.Theorem 5.
N
2
,
g
e
n
S
m
i
n
p
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove the theorem we simulate a register machineM with an S
m
i
n
p
S
S
N
P
l
o
c system Π. Prior to the construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. If register r stores the number n, then neuron σ
r has 2
n
+
2 spikes. If some instruction l
i is applied by M this means neuron σ
l
i begins simulating the instruction.
Module ADD. The template module for the ADD instruction is depicted in Figure 9. The module functions are as follows: the simulation starts from the reference neuron l
1
•
. Once l
1
• applies its rule, it sends one spike to each of neurons x
1, x
2, and r at schedule [
0,1
). Due to min-sequentiality neuron x
1 will fire next at step 2. Neuron x
1 applies its rule at schedule [
1,2
) to send a spike to each of neurons x
2 and r. Simulation of neuron r is complete now with two spikes added to its content. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on rule selection of neuron x
2. We have the following two cases depending on the rule application by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
/
a
2
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes two spikes of neuron x
2 and sends one spike to x
3. In this way, the single spike of neuron x
2 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
3 in order to begin simulating l
3 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes and sends one spike to neuron x
3. At schedule [
3,4
) both neurons x
2 and x
3 are active, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has three spike. Hence at [
3,4
), rule a
2
/
a
→
a of neuron x
2 is applied and one spike is sent to neuron x
4. At [
4,5
) both neurons x
3 and x
4 are active with equal number of spikes and due to min-pseudosequentiality both fire simultaneously, the spike fired by neuron x
3 is not received by any neuron, since neuron x
3 has no synapse at schedule [
4,5
) and the spike fired by x
4 is received by l
2. At [
5,6
) neuron l
2 becomes active to begin simulating l
2 of M.
The simulation of ADD is complete as the number of spikes in neuronr is increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. Since neuron r remains inactive when its content remains even. Hence, when simulating ADD, neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. To simulate instruction l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
) we have the SUB module in Figure 10. At schedule [
0,1
), the local reference neuron l
1
• fires sending one spike to each of neurons r, c
i
1, c
i
2, and s
1. Due to min-pseudosequentiality, both neurons c
i
1 and c
i
2 fire at [
1,2
). Neuron s
1 receives two, one each from neurons c
i
1 and c
i
2. At this point neuron σ
r has the following two cases depending on the value of n in register r.
Case I. When n
=
0, this means neuron σ
r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes, the most at [
2,3
), so neuron r fires and sends a spike to neuron s
1. At [
3,4
) neuron s
1 has 5 spikes and fires sending a spike to neuron s
3. At [
4,5
) neuron s
3 fires sending a spike to each of neurons s
1 (returning the initial spike of s
1) and l
3. Hence, system Π will simulate the next instruction l
3.
Case II. When n
≥
1, this means that neuron σ
r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron s
1 has 4 spikes, the less at [
2,3
), so s
1 applies it forgetting rule at [
2,3
)
. Neuron r fires at [
3,4
), consuming 3 spikes (to simulate the decrement of n by 1) and sending a spike to neuron s
2. At [
4,5
) neuron s
2 fires sending a spike to each of neurons s
1 (returning the initial spike of s
1) and l
2. Hence, system Π will simulate the next instruction l
2.
Due to local reference neuron, there is no interference with any SUB module. The simulation of the SUB instruction is correct: if registerr is nonempty then spikes in neuron σ
r are decreased by 2 followed by activating neuron l
2; if register r is empty then spikes in neuron σ
r are not decreased and neuron l
3 is activated. It is to be noted that the SUB module in Figure 7 for min-sequentiality can also be used in S
m
i
n
pSSN P
l
o
c systems.
Module FIN: Halting the Computation. The module FIN in Figure 8 can also be used in S
m
i
n
pSSN P
l
o
c systems to produce the output of Π.
It is clear that all three modules have utilized at most 3 rules in each neuron, consumed at most 5 spikes while forgetting at most 4 spikes. The synapses of each module are synchronized with respect to their related local reference neurons. We also note that no extended rules are needed in ADD module due to min-sequentiality, but in FIN module. The parameters of the theorem are satisfied, thus completing the proof.Figure 9
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 10
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).


## 4.1. Max-Sequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the max-sequential strategy orS
m
a
x
S
S
N
P
l
o
c systems in short. Here the superscript m
a
x stands for max-sequential and the subscript l
o
c means local scheduling. We note that for this section we make use of extended rules which are spiking rules where p
≥
2. In our results we use parameters, similar to [19] and other works on universality. Parameters r
u
l
e
i
,
f
o
r
g
j
,
c
o
n
s
k specify at most i
≥
1 rules in each neuron, forgetting at most j
≥
1 spikes and consuming at most k
≥
1 spikes, respectively.Theorem 2.
N
2
,
g
e
n
S
m
a
x
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem2, we will simulate a register machine M with an S
m
a
x
S
S
N
P
l
o
c system Π. Prior to construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. The local reference neuron is labeled with “•”. If the content of r is the number n, then spikes stored in its corresponding σ
r are 2
n
+
2. If M applies some instruction l
i such that some operation, i.e., ADD, SUB, or HALT, is performed by M this means a neuron σ
l
i begins to simulate the operation. We provide modules ADD, SUB, and FIN in order to simulate all three types of instructions of M.
Module ADD. In Figure 1 we give the graphical description of the module simulating a rule of the form l
1
:
(
A
D
D
(
r
)
,
l
2
,
l
3
).
The module functions are as follows: here the reference neuron isl
1, so it is labeled with •, i.e., l
1
•. The simulation starts from the reference neuron l
1
•. Once l
1
• applies its rule, it sends one spike to each of neurons x
1 and x
2 at schedule [
0,1
). In step 2, neuron x
1 is active with two spikes. Neuron x
1 applies its extended rule at schedule [
1,2
) to send two spikes to each of neurons x
2 and r. Neuron r now has two new spikes added to its previous spikes. If the number of spikes in neuron r is even then neuron r does not apply any rule. It is worth noting that we use here an extended rule instead of a standard rule as it is a strong sequential case, which means at most one neuron can fire at any step. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on which rule of neuron x
2 is applied. We have the following two cases depending on which rule is applied by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes all 3 spikes of neuron x
2 and sends one spike to each of neurons x
1 and x
3. In this way, the single spike of neuron x
1 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
2 in order to begin simulating l
2 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes one spike and sends one spike to each of neurons x
1 and x
3. In this way, the single spike of neuron x
1 is restored. At schedule [
3,4
) both neurons x
2 and x
3 can apply their rules, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has only one spike. Hence at [
3,4
) rule a
2
→
a of neuron x
2 is applied. At [
4,5
) neuron x
4 applies its rule to consume one spike and send one spike to each of neurons x
3 and l
3. At [
5,6
), neuron x
3 has the most spikes so it applies its forgetting rule. At [
6,7
) neuron l
3 becomes active to begin simulating l
3 of M.
The simulation of ADD is complete as the number of spikes in neuronr increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. We note that neuron r remains inactive as long as its content remains even. Hence, when simulating ADD neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. In Figure 2 we give the graphical description of the module SUB simulating a rule of the form l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
). The module functions are as follows: at schedule [
0,1
), the reference neuron l
1
• is activated and fires sending one spike to each of neurons r
,
s
1, and c
i
1. The SUB module always has two cases depending on the value n in register r: either n
=
0 (when register r is empty) or n
≥
1 (when register r is nonempty). We explain both the cases separately beginning at schedule [
1,2
).
Case I. When n
=
0 in register r, then neuron r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 and c
i
1 have 2 and 4 spikes, respectively. Due to max-sequentiality, c
i
1 is the activated neuron so it fires consuming one spike and sending a spike at [
1,2
). Due to the spiking of neuron c
i
1, neuron c
i
2 now has 4 spikes. Neuron c
i
2 is activated and it fires one spike each to s
1 and c
i
3 at [
2,3
). Neurons s
1 and c
i
3 now have 3 and 5 spikes each, respectively. Neuron c
i
3 is activated so it consumes one spike and sends a spike to neuron s
1 at [
3,4
). Now neuron s
1 has 4 spikes and applies its forgetting rule at [
4,5
). Neuron r is now activated so applying its second rule, it consumes one spike and sends it to neuron s
3 at [
5,6
). At [
6,7
) neuron s
3 fires sending a spike to neurons l
3 and s
1. Neurons r and s
1 now each have their original spikes with 2 and 1 spikes, respectively. Lastly at [
7,8
) neuron l
3 is activated to begin simulating instruction l
3 of M.
Case II. When n
≥
1 in register r, this means neuron r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron r fires sending a spike to neuron s
1 at [
1,2
) and consuming 3 spikes. Hence, neuron r now has 2
n spikes corresponding to subtracting the content of register r by 1. Neuron c
i
1 has the most spikes, so it fires sending a spike to each of neurons s
1 and c
i
3 at [
2,3
). At [
3,4
) neuron c
i
3 has the most spikes so it fires sending a spike to neuron s
1. At [
4,5
) neuron s
1 now has 5 spikes and it fires sending a spike to neuron s
2. At [
5,6
) neuron s
2 fires sending one spike each of neurons s
1 (restoring the single spike of s
1) and l
2. Lastly at [
6,7
) neuron l
2 is activated to simulate the instruction l
2 of M.
In both scenarios the module SUB is restored to its initial configuration after simulating a SUB instruction. Since a registerr in M can be associated with two or more SUB instructions, we must check for interference among several SUB modules. We find that there is no interference due to the semantics of local schedule. Let l
i and l
x be SUB instructions on register r, and let l
i be the instruction to be simulated. Neuron σ
r can have a synapse to neurons s
1 and s
3 in the modules associated with instructions l
i and l
x. Due to the local schedule of synapses, only synapses associated with the simulated instruction l
i are available. Neurons not associated with l
i are not available; hence they do not receive any spikes from σ
r. In this way, no wrong simulations are performed by Π.
Module FIN: Halting the Computation. To complete the computation, the module FIN is depicted in Figure 3. Assume that register machine M has halted; i.e., its instruction l
h has been applied. This means that Π simulates l
h and begins to output the result. Recall that register 1 is never decremented; i.e., it is never associated with S
U
B instruction. This means that σ
1 holds 2
n spikes. At [
0,1
) reference neuron l
h
• fires sending a spike to each of neurons l
h
1 and the output neuron σ
o
u
t. At [
1,2
) neuron l
h
1 fires sending a spike to neuron σ
o
u
t. At [
2,3
) neuron σ
o
u
t fires sending the first spike (out of three spikes) to the environment and to neuron σ
1. At the next step neuron σ
1 is activated since it has 2
n
+
1
≥
3 spikes. For the next n steps neuron σ
1 continues to apply its rule to consume 2 spikes. After n
+
1 steps neuron σ
1 has only one spike so at this step neuron σ
o
u
t spikes sending a spike to the environment for the second and last time. Finally at step n + 2, neuron σ
1 forgets its last spike. The first and second spike of neuron σ
o
u
t were sent out at step t and t
+
n
+
1, respectively. Hence the result of the computation of Π is (
t
+
n
+
1
)
-
t
-
1
=
n, exactly the value in register r when register machine M halts. All parameters for r
u
l
e, f
o
r
g, and c
o
n
s are satisfied, and an extended rule is used in ADD module. This completes the proof.Figure 1
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 2
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).Figure 3
Module FIN.In what follow, we consider max-pseudosequential strategy: a more realistic approach of spiking for neurons in the system: in case of a tie among active neurons, then all the tied neurons will fire simultaneously.


## 4.2. Max-Pseudosequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the max-pseudosequential strategy, abbreviated asS
m
a
x
p
S
S
N
P
l
o
c systems.Theorem 3.
N
2
,
g
e
n
S
m
a
x
p
S
S
N
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem3, we simulate a register machine M with an S
m
a
x
p
S
S
N
P
l
o
c system Π. Prior to the construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. If register r stores the number n, then neuron σ
r has 2
n
+
2 spikes. If some instruction l
i is applied by M this means neuron σ
l
i begins simulating the instruction. In contrast to Theorem 2, in Theorem 3, due to max-pseudosequentiality we do not need extended rules; only standard rules are enough to prove universality.
Module ADD. The template module for the ADD instruction is depicted in Figure 4. The local reference neuron l
1
• fires at schedule [
0,1
) sending one spike to each of neurons x
1, x
2, and x
3. At [
1,2
) there is a tie between neurons x
1 and x
2 (both have equal number of spikes), but due to max-pseudosequentiality, both neurons fire simultaneously and both send one spike each to neurons x
3 and r. In this way neuron σ
r receives two spikes corresponding to an increment of 1 in the stored value in register r. At the next step neuron x
3 must nondeterministically decide which rule to apply, so we have the following two cases.
Case I. When neuron x
3 applies rule a
3
→
a at [
2,3
), one spike is sent to neuron x
4. Neuron x
4 fires sending a spike to neuron l
2 at [
3,4
), which means system Π will simulate the next instruction l
2 of M.
Case II. When neuron x
3 applies its rule a
3
/
a
→
a it consumes one spike, so two spikes remain. Neuron x
4 receives a spike from neuron x
3 but cannot fire since neuron x
3 still has the most spikes. At [
3,4
) neuron x
3 applies a
2
→
a firing and sending a spike to neuron x
5. Again there is a tie between neurons x
4 and x
5 at [
4,5
) but due to max-pseudosequentiality both fires at a single step, sending a spike but only l
3 receives a spike; the spike of x
4 is wasted as there is no synapse from it at schedule [
4,5
). This means system Π is ready to simulate the next instruction l
3 of M.
The simulation of an ADD instruction is correct: contents ofσ
r are increased by two, followed by nondeterministically activating either neuron l
2 or l
3.
Module SUB. To simulate instruction l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
) we have the SUB module in Figure 5. At schedule [
0,1
) the local reference neuron l
1
• fires sending one spike to each of neurons c
i
1, c
i
2, and s
1. At the next step neurons c
i
1, c
i
2, and s
1 have 1, 1, and 2 spikes, respectively. Due to max-pseudosequentiality, both tied neurons c
i
1 and c
i
2 with equal number of spikes fire simultaneously at [
1,2
). Neuron r receives one spike from neuron c
i
1 while neuron s
1 receives two, one each from neurons c
i
1 and c
i
2. At this point neuron σ
r has the following two cases depending on the value of n in register r.
Case I. When n
=
0, this means neuron σ
r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes, the most at [
2,3
) so it applies its forgetting rule. At [
3,4
) neuron r applies its rule consuming and producing one spike, sending the spike to neuron s
3. In this way the spikes in σ
r return to 2
n
+
2 indicating n
=
0 in register r. At [
4,5
) neuron s
3 fires and so Π begins to simulate the next instruction l
3.
Case II. When n
≥
1, this means that neuron σ
r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron r fires at [
2,3
), consuming 3 spikes (to simulate the decrement of n by 1) and sending a spike to neuron s
1. At [
3,4
) neuron s
1 has 5 spikes and fires sending a spike to neuron s
2. At [5,6) neuron s
2 fires send one spike each to neurons s
1 (restoring the single spike of s
1) and l
2. Hence, system Π will simulate the next instruction l
2.
As due to the semantics of local reference neuron, there is no interference with any SUB module. The simulation of the SUB instruction is correct: if registerr is nonempty then spikes in neuron σ
r are decreased by 2 followed by activating neuron l
2; if register r is empty then spikes in neuron σ
r are not decreased and neuron l
3 is activated. It is to be noted that with slight high complexity the SUB module in Figure 2 for max-sequentiality can also be used in M
m
a
x
pSSN P
l
o
c systems.
Module FIN: Halting the Computation. The module FIN in Figure 3 can also be used in M
m
a
x
pSSN P
l
o
c systems to produce the output of Π.
It is clear that all three modules have utilized at most 3 rules in each neuron, consumed at most 5 spikes while forgetting at most 4 spikes. The synapses of each module are synchronized with respect to their related local reference neurons. We also note that no extended rules are needed in max-pseudosequentiality. The parameters of the theorem are satisfied, thus completing the proof.Figure 4
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 5
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).


## 4.3. Min-Sequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the min-sequential strategy orS
m
i
n
S
S
N
P
l
o
c systems in short. Here the superscript m
i
n stands for min-sequential and the subscript l
o
c means local scheduling. We note that, due to min-sequentiality, in ADD module we do not make use of extended rules as compared to Theorem 2. Extended rule is used only in FIN module. In our results we use parameters, similar to [19] and other works on universality. Parameters r
u
l
e
i
,
f
o
r
g
j
,
c
o
n
s
k specify at most i
≥
1 rules in each neuron, forgetting at most j
≥
1 spikes, and consuming at most k
≥
1 spikes, respectively.Theorem 4.
N
2
,
g
e
n
S
m
i
n
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove Theorem4, we will simulate a register machine M with an S
m
i
n
S
S
N
P
l
o
c system Π. Prior to construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. The local reference neuron is labeled with “•”. If the content of r is the number n, then spikes stored in its corresponding σ
r are 2
n
+
2. If M applies some instruction l
i such that some operation, i.e., ADD, SUB, or HALT, is performed by M this means a neuron σ
l
i begins to simulate the operation. We provide modules ADD, SUB, and FIN in order to simulate all three types of instructions of M.
Module ADD. In Figure 6 we give the graphical description of the module simulating a rule of the form l
1
:
(
A
D
D
(
r
)
,
l
2
,
l
3
).
The module functions are as follows: the simulation starts from the reference neuronl
1
•
. Once l
1
• applies its rule, it sends one spike to each of neurons x
1, x
2, and r at schedule [
0,1
). It is worth noting that, in order to keep neuron r inactive, its content must be even; adding one spike to the content of register r means that it is active to fire now, but due to min-sequentiality neuron x
1 will fire next at step 2. Neuron x
1 applies its rule at schedule [
1,2
) to send a spike to each of neurons x
2 and r. Neuron r has now one more spike added to its previous spikes. As the number of spikes in neuron r is even now so it will not apply any rule. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on which rule of neuron x
2 is applied. We have the following two cases depending on which rule is applied by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
/
a
2
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes two spikes of neuron x
2 and sends one spike to x
3. In this way, the single spike of neuron x
2 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
3 in order to begin simulating l
3 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes and sends one spike to neuron x
3. At schedule [
3,4
) both neurons x
2 and x
3 are active, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has three spike. Hence at [
3,4
), rule a
2
/
a
→
a of neuron x
2 is applied and one spike is sent to neuron x
4. At [
4,5
) both neurons x
3 and x
4 are active, but only neuron x
3 with less spikes applies its rule; the spike fired by neuron x
3 is not received by any neuron, since neuron x
3 has no synapse at schedule [
4,5
). At [
5,6
), neuron x
4 fires sending a spike to l
2. At [
6,7
) neuron l
2 becomes active to begin simulating l
2 of M.
The simulation of ADD is complete as the number of spikes in neuronr is increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. Since neuron r remains inactive as long as its content remains even. Hence, when simulating ADD neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. In Figure 7 we give the graphical description of the module SUB simulating a rule of the form l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
). The module functions are as follows: At schedule [
0,1
), the reference neuron l
1
• is activated and fires sending one spike to each of neurons r
,
s
1 and c
i
1. Due to min-sequentiality, c
i
1 is the activated neuron so it fires and sends a spike at [
1,2
). Due to the spiking of neuron c
i
1, neurons s
1 and c
i
2 now have 3 and 1 spikes, respectively. Neuron c
i
2 is activated and it fires one spike to s
1 at [
2,3
).
The SUB module always has two cases depending on the valuen in register r: either n
=
0 (when register r is empty) or n
≥
1 (when register r is nonempty). We explain both cases separately beginning at schedule [
3,4
).
Case I. When n
=
0 in register r, then neuron r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes. Neuron r is now activated with less spikes so applying its second rule, it consumes one spike and sends it to neuron s
1 at [
3,4
). At [
4,5
) neuron s
1 fires sending a spike to neuron s
3. At [
5,6
) neuron s
3 fires sending a spike to s
1 and l
3. Neurons r and s
1 now each have their original spikes with 2 and 1 spikes, respectively. Lastly at [
6,7
) neuron l
3 is activated to begin simulating instruction l
3 of M.
Case II. When n
≥
1 in register r, this means neuron r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron s
1 has 4 spikes, the less at [
3,4
) so it applies its forgetting rule. Neuron r fires sending a spike to neuron s
2 at [
4,5
) and consuming 3 spikes. Hence, neuron r now has 2
n spikes corresponding to subtracting the content of register r by 1. At [
5,6
) neuron s
2 fires sending one spike to each of neurons s
1 (restoring the single spike of s
1) and l
2. Lastly at [
6,7
) neuron l
2 is activated to simulate the instruction l
2 of M.
In both scenarios the module SUB is restored to its initial configuration after simulating a SUB instruction. There is no interference in this module due to the semantics of local scheduling.
Module FIN: Halting the Computation. To complete the computation, the module FIN is depicted in Figure 8. Assume that register machine M has halted; i.e., its instruction l
h has been applied. This means that Π simulates l
h and begins to output the result. At [
0,1
) reference neuron l
h
• fires sending a spike to the output neuron σ
o
u
t. At [
1,2
) neuron σ
o
u
t fires sending the first spike (hence t
1) out of three spikes to the environment and to neuron σ
1. At the next step neuron σ
1 is activated since it has 2
n
+
1
≥
3 spikes. For the next n steps neuron σ
1 continues to apply its extended rule to consume and produce 2 spikes. At n
+
1 step, neuron σ
1 has only one spike so by applying second rule neuron σ
1 spikes sending one spike to neuron σ
o
u
t (hence activating it for the second time with odd number of spikes). At n
+
2 step, neuron σ
o
u
t spikes (hence t
2) sending a spike to the environment for the second and last time. The first and second spike of neuron σ
o
u
t were sent out at step t and t
+
n
+
2, respectively. Hence the result of the computation of Π is (
t
+
n
+
2
)
-
t
-
2
=
n, exactly the value in register r when register machine M halts. All parameters for r
u
l
e, f
o
r
g, and c
o
n
s are satisfied, and an extended rule is used in FIN module. This completes the proof.Figure 6
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 7
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).Figure 8
Module FIN.


## 4.4. Min-Pseudosequential SN P Systems with Local Scheduled Synapses without Delays

In this section we provide the universality results of SSSN P systems with local schedules and without delays in the min-pseudosequential strategy, abbreviated asS
m
i
n
p
S
S
N
P
l
o
c systems.Theorem 5.
N
2
,
g
e
n
S
m
i
n
p
S
S
N
e
P
l
o
c
(
r
u
l
e
3
,
f
o
r
g
4
,
c
o
n
s
5
)
=
N
R
E.Proof.
In order to prove the theorem we simulate a register machineM with an S
m
i
n
p
S
S
N
P
l
o
c system Π. Prior to the construction of Π, we give a brief description of the computation as follows: each neuron σ
r in Π is associated with each register r in M. If register r stores the number n, then neuron σ
r has 2
n
+
2 spikes. If some instruction l
i is applied by M this means neuron σ
l
i begins simulating the instruction.
Module ADD. The template module for the ADD instruction is depicted in Figure 9. The module functions are as follows: the simulation starts from the reference neuron l
1
•
. Once l
1
• applies its rule, it sends one spike to each of neurons x
1, x
2, and r at schedule [
0,1
). Due to min-sequentiality neuron x
1 will fire next at step 2. Neuron x
1 applies its rule at schedule [
1,2
) to send a spike to each of neurons x
2 and r. Simulation of neuron r is complete now with two spikes added to its content. At the next step neuron x
2 nondeterministically selects which rule to apply. Either neuron l
2 or l
3 becomes activated depending on rule selection of neuron x
2. We have the following two cases depending on the rule application by neuron x
2.
Case I. If neuron x
2 applies its rule a
3
/
a
2
→
a, then neuron x
2 fires only once, at schedule [
2,3
). Applying this rule consumes two spikes of neuron x
2 and sends one spike to x
3. In this way, the single spike of neuron x
2 is restored. At the next step x
3 is the only neuron that can apply a rule at schedule [
3,4
). A spike is sent from neuron x
3 to neuron l
3 in order to begin simulating l
3 of M.
Case II. If neuron x
2 applies its rule a
3
/
a
→
a, then neuron x
2 fires twice. By firing first at step 3, neuron x
2 consumes and sends one spike to neuron x
3. At schedule [
3,4
) both neurons x
2 and x
3 are active, but only neuron x
2 can apply its rule since it has two spikes while neuron x
3 has three spike. Hence at [
3,4
), rule a
2
/
a
→
a of neuron x
2 is applied and one spike is sent to neuron x
4. At [
4,5
) both neurons x
3 and x
4 are active with equal number of spikes and due to min-pseudosequentiality both fire simultaneously, the spike fired by neuron x
3 is not received by any neuron, since neuron x
3 has no synapse at schedule [
4,5
) and the spike fired by x
4 is received by l
2. At [
5,6
) neuron l
2 becomes active to begin simulating l
2 of M.
The simulation of ADD is complete as the number of spikes in neuronr is increased by two, hence increasing the content of register r by 1. Afterwards, the next instruction, either l
2 or l
3, is chosen nondeterministically for simulation. Since neuron r remains inactive when its content remains even. Hence, when simulating ADD, neuron r does not apply any of its rules. The simulation ends by restoring all spikes in all neurons to their initial configuration. Hence, the module is ready for another simulation of ADD.
Module SUB. To simulate instruction l
1
:
(
S
U
B
(
r
)
,
l
2
,
l
3
) we have the SUB module in Figure 10. At schedule [
0,1
), the local reference neuron l
1
• fires sending one spike to each of neurons r, c
i
1, c
i
2, and s
1. Due to min-pseudosequentiality, both neurons c
i
1 and c
i
2 fire at [
1,2
). Neuron s
1 receives two, one each from neurons c
i
1 and c
i
2. At this point neuron σ
r has the following two cases depending on the value of n in register r.
Case I. When n
=
0, this means neuron σ
r has (
2
n
+
2
)
+
1
=
3 spikes. Neuron s
1 has 4 spikes, the most at [
2,3
), so neuron r fires and sends a spike to neuron s
1. At [
3,4
) neuron s
1 has 5 spikes and fires sending a spike to neuron s
3. At [
4,5
) neuron s
3 fires sending a spike to each of neurons s
1 (returning the initial spike of s
1) and l
3. Hence, system Π will simulate the next instruction l
3.
Case II. When n
≥
1, this means that neuron σ
r has (
2
n
+
2
)
+
1
≥
5 spikes. Neuron s
1 has 4 spikes, the less at [
2,3
), so s
1 applies it forgetting rule at [
2,3
)
. Neuron r fires at [
3,4
), consuming 3 spikes (to simulate the decrement of n by 1) and sending a spike to neuron s
2. At [
4,5
) neuron s
2 fires sending a spike to each of neurons s
1 (returning the initial spike of s
1) and l
2. Hence, system Π will simulate the next instruction l
2.
Due to local reference neuron, there is no interference with any SUB module. The simulation of the SUB instruction is correct: if registerr is nonempty then spikes in neuron σ
r are decreased by 2 followed by activating neuron l
2; if register r is empty then spikes in neuron σ
r are not decreased and neuron l
3 is activated. It is to be noted that the SUB module in Figure 7 for min-sequentiality can also be used in S
m
i
n
pSSN P
l
o
c systems.
Module FIN: Halting the Computation. The module FIN in Figure 8 can also be used in S
m
i
n
pSSN P
l
o
c systems to produce the output of Π.
It is clear that all three modules have utilized at most 3 rules in each neuron, consumed at most 5 spikes while forgetting at most 4 spikes. The synapses of each module are synchronized with respect to their related local reference neurons. We also note that no extended rules are needed in ADD module due to min-sequentiality, but in FIN module. The parameters of the theorem are satisfied, thus completing the proof.Figure 9
Module ADD: simulating instructionl
1
:
(
A
D
D
(
r
)
:
l
2
,
l
3
).Figure 10
Module SUB: simulating instructionl
1
:
(
S
U
B
(
r
)
:
l
2
,
l
3
).


## 5. Final Remarks

In this work, the computational power of sequential SN P systems with local scheduled synapses without delay is investigated. Results show that sequential SN P systems with local scheduled synapses without delay working in both max/min-sequentiality and max/min-pseudosequentiality strategies are computationally universal with both standard and extended rules (only in case when standard rules fail to perform). In particular, we showed for both strategies that universality is achieved using at most 3 rules per neuron, consuming, and forgetting at most 5 and 4 spikes, respectively. We further note that extended rule is used only in ADD module with the max-sequential strategy and FIN module with both min-sequential and min-pseudosequential strategies. Moreover strong sequential strategy has slight higher complexity than pseudosequential.Our future work is to prove universality of our variants with global-scheduled synapses. The open problems are to reduce complexity of our systems, to prove universality without forgetting rules and extended rules.The other direction that might be interesting is to realize which class of problems/languages these kind of SN P systems variant is capable of solving/deciding, thereby comparing its capability in recognizing/solving languages/problems with the other variants with respect to several parameters/ingredients of the SN P systems.



---

*Source: 7313414-2019-04-14.xml*