Spiking neural P systems: main ideas and results

Membrane systems, also called P systems, introduced by Gh. Păun in Păun (2000) are a branch of the wide area of natural computing, or bioinspired computing, that has developed considerably over the past 20 years, with deep theoretical results and significant applications. Motivations, basic definitions and main results can be found in Păun (2002), in the Oxford Handbook of Membrane Computing (Păun et al. 2009) and in the Web site of membrane computing (Systems 2008).

In its original definition (Păun 2000), a P system consists of a membrane structure composed by several cell-membranes, hierarchically embedded in a main membrane called the skin membrane. The membranes delimit regions and can contain objects, which evolve according to given evolution rules associated with the regions.

Variants of this model were soon developed, taking into account different aspects of the cells physiology and of cells arrangement and interactions. In particular, (Martin-Vide et al. 2003) introduced tissue P systems, substituting the tree-like hierarchical organization of membranes with a structure where cells with a single membrane are arranged in the nodes of an undirected graph. A further evolution led to the definition of Spiking Neural P systems (in short, SN P systems), with cells/neurons arranged in the nodes of a directed graph, whose arcs mimic the synapses of animal neural systems, and communicating through electrical impulses of identical form, called spikes (Ionescu et al. 2006).

In this paper we will present, with a tutorial approach, the main ideas underlying the definition of SN P systems and the most interesting variants that have been proposed in the literature. In particular, we will discuss the results concerning the computational power of these models, both in terms of Turing completeness and of efficiency in solving hard problems.

The paper is organized as follows. In the next section we will discuss the biological inspiration behind the introduction of SN P systems, illustrating in an informal way their main characteristics and features. The formal definition in its original (standard) form (Ionescu et al. 2006) and the corresponding notion of computation in SN P systems will follow in Sect. 3. In particular, we will consider the different modes in which the systems can compute, recognizing or accepting numbers or languages on a binary alphabet, or computing functions, and the different ways to provide input information, if any, and to read output results.

In the seminal paper (Ionescu et al. 2006) the computational power of the basic model of SN P systems has been analyzed, giving interesting results concerning the universality, or Turing completeness, of SN P systems, that are presented in Sect. 4. The main proof technique, based on the construction of SN P systems able to simulate register machines, which are known to be Turing complete, is illustrated.

Starting from these initial definitions and results, the world of SN P systems has been populated by a remarkable variety of different specimens, with different features (in general motivated by biology) and different power that have been deeply analyzed. In the next sections, the main variants will be presented: different kinds of rules, in particular extended rules (Sect. 5); different ways or strategies to select the rules to be fired (Sect. 6); use of weights, thresholds, or rules on synapses (Sect. 7); use of astrocytes (Sect. 8); systems with structural plasticity (Sect. 9). In Sect. 10 we will consider the computational power of SN P systems not from the point of view of universality, or of the families of sets of numbers or of languages they can generate/accept under specific bounds on the main parameters of the system, but looking at how they can be used to efficiently solve hard problems. We end the paper with some concluding remarks and open problems in Sect. 11.

We assume the reader to have some familiarity with formal languages and automata theory, for which we refer to Rozenberg and Salomaa (1997). We just list a few notions and notations. An alphabet V is a finite set of symbols, and \(V^*\) denotes the free monoid generated by V, that is the set \(V^+\) of all finite sequences of symbols from V, called words, equipped with the operation of concatenation, that associates with the words \(v=v_1 \dots v_n\) and \(w=w_1 \dots w_m\) their concatenation \(vw = v_1 \dots v_n w_1 \dots w_m\), with the empty string, denoted by \(\lambda\), as unit element. A regular expression over an alphabet V is defined as follows: (i) \(\lambda\) and each \(a \in V\) is a regular expression; (ii) if \(E_1, E_2\) are regular expressions over V, then \((E_1)(E_2), (E_1) \cup (E_2)\), and \((E_1)^+\) are regular expressions over V; and (iii) nothing else is a regular expression over V. Notice that the parentheses are not in V. They are used to make explicit the order of application of the operators in a regular expression; in case they are not necessary, they can be omitted. Also, \(E_1^+ \cup \lambda\) can be written as \(E_1^*\). With each regular expression E we associate the regular language L(E) as follows: (i) \(L(\lambda ) = \{\lambda \}\), \(L(a) = \{a\}\), for \(a \in V\); (ii) \(L((E_1)(E_2)) = L(E_1)L(E_2)\), \(L((E_1) \cup (E_2)) = L(E_1) \cup L(E_2)\), and \(L((E_1)^+) = L(E_1)^+\), for all regular expressions \(E_1, E_2\).

Various attempts to mimic the way a human brain works have been carried out, mainly based on various types of Artificial Neural Networks (ANNs) (Gurney 1997). In an Artificial Neural Network, simple computing elements, called neurons, receive input signals from other neurons through connections, called synapses, process them using a non-linear function of the weighted sum of inputs, and communicate the result as an output signal sent to connected neurons, following a global discrete clock. Synapses have some weights associated, that are used to increase or decrease the strength of signals crossing them. An ANN can learn by examples, modifying the weights on synapses so as to minimize the error rate on the output. In the last few decades, ANNs assumed a central role in supervised machine learning, and became a fundamental tool in many application areas.

An important aspect not considered in this basic model of ANNs concerns the complex temporal dynamics of biological neurons. For this reason, in Maass (1997), Maass and Bishop (1999), Maass (2002) an abstract discrete model of computation in Artificial Neural Networks based on spikes, called Spiking Neural Networks (SNNs), has been introduced.

SNNs are Artificial Neural Networks trying to mimic more closely the functioning of natural neurons, in particular by considering the use of time steps. In fact, in a SNN the signals are represented as discrete events with a uniform intensity (the spikes), transferring a unit of information, and are not transmitted at each propagation cycle (as usually done with ANNs), but instead a signal is sent out only when a membrane potential becomes greater than a defined threshold. In other words, when the membrane potential (resulting from the input signals) reaches the threshold, the neuron fires, thus producing a spike that is communicated to adjacent neurons, changing in this way their potential. The time when a signal is emitted becomes, as a consequence, crucial for the result of the computation.

Ideas from both ANNs and SNNs have been incorporated in the area of P systems quite early. In particular, in Martin-Vide et al. (2003), inspired by the standard knowledge about neuron functioning and the way the inter-cellular communication takes place, tissue-like P systems were introduced, where the cells-membranes are organized as nodes of a graph instead than of a hierarchical tree. Similarly to ANNs, tissue-like P systems do not consider time aspects related to the signal issuing, and intervals between signals.

Spiking Neural P systems, in short SN P systems, were thus introduced in Ionescu et al. (2006), as a new variant of P systems where time plays a fundamental role in computation.

Informally, an SN P system consists of a set of neurons (that can be regarded as cells with a single membrane) placed in the nodes of a directed graph. A neuron can hold any number of spikes (a spike is denoted in what follows by the symbol a) and, under some specific conditions depending on the number of spikes within the neuron itself, it can fire, producing one spike that will be sent, possibly with some delay, along the arcs of the graph, representing the synapses, to all adjacent (post-synaptic) neurons. Starting from an initial configuration, represented by the number of spikes contained in each neuron, and following given rules, the system can hence evolve and possibly output some information.

Let us now look at some of the most interesting variants of SN P systems that have been considered.

A first generalization of the “standard” rules was introduced in Ionescu et al. (2006) and Păun and Păun (2007) as a way to reduce the dimension (number of neurons) of an universal SN P system, and then more precisely presented in Chen et al. (2008) under the name of extended rules. The corresponding systems were defined as follows:

Using criteria similar to the standard ones, a rule \(E/a^c\rightarrow a^p\) is enabled if the associated neuron contains \(k \ge c\) spikes, and \(a^k \in L(E)\). While a standard rule, when applied, consumes c spikes and produces exactly one spike (spiking rules) or no spikes (forgetting rules), extended rules can produce any number \(p\ge 0\) of spikes, consuming c spikes. Being \(p \ge 0\), we obtain a generalization of both standard spiking and forgetting rules, with the additional feature of having the forgetting rules also controlled by regular expressions. Moreover, forgetting rules are now allowed to compete in a non-deterministic way with spiking rules. Note that with this definitions there are no delays between firing and spiking, hence the produced spikes are immediately delivered.

Possible ways to encode information, non-deterministic choice among two or more enabled rules in a neuron, configurations, transitions, computations, generation or acceptance of numbers are defined just as in standard SN P systems.

Spike trains can be defined in two different ways. Following the standard definition, if the output neuron spikes, then we write 1, independently of the number p of spikes emitted, otherwise we write 0. Alternatively, we can also consider spike trains as encoding words on an arbitrary alphabet, associating the symbol \(b_i\) with a step when the output neuron emits \(i\ge 1\) spikes. Steps when no spikes are emitted can be associated to a symbol \(b_0\) in the alphabet or to the empty string \(\lambda\). In the first case we denote the language generated by a system \(\varPi\) by \(L_{res}(\varPi )\) (with” res” coming from “restricted”), in the latter one we write \(L_\lambda (\varPi )\).

The universality of extended SN P systems (\(SN^eP\) systems) as number generators can be proved as usual through simulation of register machines, in a simpler way Chen et al. (2008):

This means that the family of recursively enumerable sets of natural numbers can be generated by extended SN P systems with unbound number of neurons, at most 4 rules in each neuron, at most 5 spikes consumed and at most 2 spikes produced by any rule.

If we look at the minimal number of neurons needed to obtain universality, extended rules give some advantage with respect to standard ones (Păun and Păun 2007).

In a similar way, the results on minimal universal computing SN P systems can be improved if extended rules are used:

The proofs are based on simulating a small universal register machine from Korec (1996), with a fine tuning of the number of used neurons.

Let’s now focus on a second relevant feature of SN P systems, that is the way rules to be executed in a given computation step are selected. As described in Sect. 3, in standard SN P systems all neurons evolve in parallel, synchronized by a global clock, but inside each neuron only at most one rule can be applied at each computation step, non-deterministically selected among all enabled rules. This type of application of rules is usually defined as sequential, at single neuron level.

Various works have appeared that consider different strategies, or different semantics, for the application of the rules inside the neurons.

A first alternative strategy, that has been considered in Leporati et al. (2007), is the maximally parallel semantics, intended exactly as in cell-like P systems. Let us denote by k the number of spikes contained in a neuron at time t. We can ideally divide the computation step in two parts. We first select, in a non-deterministic way, one rule of the neuron to be applied. If such a rule consumes c spikes, after (ideally) removing these spikes from the neuron, the rule selection process is repeated, considering the remaining \(k-c\) spikes, until no further rule can be applied. In this way, a rule may be chosen many times to be applied, and thus at the end of the process we will have a multiset of rules that will be simultaneously fired. A little technical difficulty is given by the fact that the chosen rules may have different delays; hence, we define the delay associated with a multiset of rules as the maximum of the delays that appear in the rules. As we will better discuss in Sect. 10, dedicated to the efficiency of SN P systems in solving hard problems, this strategy has been considered in order to enhance this efficiency. In fact, we will see that NP-complete problems can be solved by SN P systems in polynomial time (and exponential space), by exploiting the intrinsic parallelism of such systems. Nonetheless, the systems must be initialized with an exponential amount of spikes. In particular, in Leporati et al. (2007) it was proved that, by using maximal parallelism, any integer number in the usual binary notation, received as an input by a SN P system, can be translated to the unary form in polynomial time, by producing a corresponding amount of spikes. As a consequence, we can build a system that is able to first generate the required amount of spikes, and then to solve the considered NP-complete problem. In the same paper, it was also proved that the conversion from binary to unary notation cannot be performed in polynomial time when the use of maximal parallelism is forbidden.

Another kind of semantics that has been considered is the exhaustive mode (Ionescu et al. 2007), assuming extended rules. In this case, at every step of computation one of the enabled rules in each neuron is non-deterministically chosen, and then applied as many times as possible, on the basis of the amount of spikes in the neuron. Hence, the number of spikes produced in that neuron in a computation step can be arbitrarily large. Note that the enabling condition is checked only on the total number of spikes in the neuron, and not on the ‘ideal’ number of spikes remaining at each substep of the selection phase. Similar results as in the case of sequential application of rules are obtained, in particular concerning computational completeness, both for number generating mode and for number accepting mode. Nonetheless, the systems required to obtain such results are, in general, significantly more complex than systems that use sequential semantics. As stated by the authors of the paper, the main reason of this complexity is related to the difficulty of simulating intrinsically sequential devices such as register machines by using a parallel application of rules. In Zhang et al. (2010) a small universal system of this type with 125 neurons, using standard rules without delays and encoding the output as length of the interval between two spikes of the output neuron, was shown. One extra neuron (126 in total) is needed if the result of the computation is given by the total number of spikes of the output neuron. The result has been improved in Pan and Zeng (2011), where a universal system with exhaustive use of rules, using only 36 neurons, has been obtained.

A semantics in between the sequential and the exhaustive mode, called generalized use of rules, was considered in Zhang et al. (2014): in each neuron, one of the applicable rules is chosen in a non-deterministic way, and then applied for a number of times also non-deterministically chosen. In this case, the authors proved that the number of neurons is fundamental to achieve a desired computational power. In fact, SN P systems using rules according to this semantics and consisting of one neuron characterize finite sets of natural numbers. When exactly two neurons are used, then the computational power of the systems is improved, but limited to the possibility to generate semilinear sets of numbers. When three neurons can be used, then at least a non-semilinear set of numbers can be generated. If no bound on the number of neuron is set, then SN P systems using this semantics are computationally complete. In Jiang et al. (2019) an improved universal system of this type was obtained, where each neuron contains at most 5 rules, each spiking rule consumes at most 4 spikes, and each forgetting rule deletes at most 4 spikes.

Yet another possibility, based on the ideas used in tissue-like P systems, is to apply rules according to a so-called flat maximal parallelism (Pan et al. 2016): at every computation step, the rules chosen to be executed in each neuron form a maximal set, to which no further applicable rule can be added; nonetheless, each rule in the set is applied only once. In Wu and Jiang (2021) authors show that SN P systems working in the flat maximally parallel mode are Turing universal as number generating devices. Moreover, it is proved that 68 neurons are sufficient to construct a universal SN P system working in the flat maximally parallel mode.

A more restrictive strategy that has been proposed in Ibarra et al. (2006) extends sequentiality also at system level: we will call this the strong sequential mode. In this mode, at every step of the computation, if there is at least one neuron with at least one rule that is enabled, we only allow one such neuron and one such rule (both chosen non-deterministically) to be fired. It was shown in Ibarra et al. (2006) that certain classes of strongly sequential SN P systems are equivalent to partially blind counter machines (see Greibach (1978) for definitions), while others are universal.

Finally, in Cavaliere et al. (2008) and Cavaliere et al. (2009), based on the observation that our biological neural systems are not synchronized, the synchronization between neurons is removed, and the power of asynchronous spiking neural P systems is investigated. More precisely, in such systems, a global clock is still present, but neurons work asynchronously in the sense that the execution of rules in each neuron is not forced to happen at a specific time instant. At each time step instead any neuron containing enabled rules may (non-deterministically) choose whether or not to fire (at most) one of them. If the content of the neuron is not changed, a rule which was enabled, and not fired, at step t can fire later. If new spikes are received, then it is possible that the unfired rule is no more enabled, while other rules will be enabled - and can be applied or not. Since the asynchronicity applies also to the output neuron, the distance in time between the first two spikes sent out by the system has now elements of randomness, and cannot be used as the result of the computation. Hence, for non-synchronized SN P systems, we will assume as the result of the computation the total number of spikes sent out to the environment. This makes it necessary to consider only halting computations. The synchronization is in general a powerful feature, and removing it seems to cause a significant reduction in computational power of asynchronous standard SN P systems, whose universality has not been proved: it remains an open problem, with a feeling in favour of non-universality. However, it turns out that the loss in power entailed by removing the synchronization is compensated by the use of extended rules. In fact, in the above papers it has been proved that a set \(Q \subseteq \mathbb {N}\) of natural numbers is recursively enumerable (i.e. \(Q \in NRE\)) if and only if it can be generated by an asynchronous SN P system with extended rules, with or without delays, with an unbound number of neurons. Moreover, finite languages and recursively enumerable languages were shown to be characterized by asynchronous SN P systems in Zhang et al. (2009).

The asynchronous operating mode has been considered for most of the variants we will discuss here: asynchronous SN P systems with structural plasticity in Cabarle et al. (2015); asynchronous extended SN P systems with astrocytes in Pan et al. (2012); asynchronous SN P systems with rules on synapses in Song et al. (2015). Furthermore, the notion of local synchronization was introduced in Song et al. (2013), and the constructed systems were proved to be computationally complete in the generating case.

In Binder et al. (2007) it was observed that in animal nervous system an important role in modulating synaptic transmission is played by astrocytes. Astrocytes are star-shaped glial cells in the brain and spinal cord that perform many functions, including biochemical control of endothelial cells that form the blood-brain barrier, regulation of cerebral blood flow, provision of nutrients to the nervous tissue, maintenance of extracellular ion balance, modulation of neuronal excitability and synaptic transmission, with both an excitatory and an inhibitory action. Hence, in Binder et al. (2007) and Păun (2007) the SN P systems with astrocytes (SNPA systems) were proposed to take into account the joint action of the two interacting networks of neurons and astrocytes.

While (Binder et al. 2007) introduces two kinds of astrocytes, excitatory and inhibitory, Păun (2007) considers a much simplified version of SNPAs, with only inhibitory astrocytes. The basic idea is adding to the system a set of astrocytes, each one of them controlling a subset of synapses. If at computation step t two or more spikes are transmitted along the synapses controlled by the astrocyte x, then exactly one spike is selected, non-deterministically, to reach the destination neuron, while all others are removed (obviously, in the case of 0 or 1 transmitted spikes x does not intervene). Hence a new degree of non-determinism is added to the functioning of the system by the branching due to the non-deterministic choice of the surviving spike. A second relevant observation is that, since the same synapse can be controlled by several astrocytes, it is possible that their action is contradictory, with a resulting deadlock of the system: in fact an astrocyte could decide to suppress a spike on the common synapse, and another to let it survive. A simple example of deadlock can be found in the paper Păun (2007), that focuses on the deadlock decidability problem, proving that it is undecidable whether an arbitrary SN P system with (at least three) astrocytes reaches a deadlock. On the other side, any SN P system with astrocytes controlling several synapses, without forgetting rules, can be reduced to an equivalent system in normal form with each astrocyte controlling only two synapses.

In Pan et al. (2012), starting from the observation that, in a biological nervous system, the same astrocyte can have an excitatory or inhibitory role, depending on the spike traffic along the supervised synapses, a slightly different definition is given. In the following we will refer to this definition.

In SNPA systems, the neurons execute the rules as in standard SN P systems at each time step, then astrocytes intervene, exercising their function of spike traffic control. Each astrocyte \(ast_i\) counts the number k of neurons that are requesting to cross the synapses in the set \(syn_{ast_i}\), then uses its threshold \(t_i\) to decide its role: Even with this definition the deadlock problem must be addressed, since it is possible that two or more astrocytes control the same synapse. In this case, if all these astrocytes have an excitatory role, then the spike along this synapse, if any, will pass to the destination neuron; if at least one of these astrocytes has an inhibitory role, then the spike will be suppressed.

The computational power of SN P systems can also be considered from a different point of view, their capability to efficiently solve computationally hard problems. This point of view has been assumed for example in Chen et al. (2006), where a variant of spiking neural P systems which have, in their initial configuration, an arbitrarily large number of inactive neurons which can be activated (in an exponential number) in polynomial time. Using this model of P systems we can deterministically solve the satisfiability problem (SAT) in constant time, so trading space for time.

In Leporati et al. (2007), a solution for the NP-complete problem Subset Sum in a constant number of computation steps was proposed, by means of a non-deterministic SN P system with extended rules.

The Subset Sum problem can be defined as follows. Problem: Subset Sum.When we allow to non-deterministically choose the rules to be applied within a neuron, then we are able to define an SN P system like the one depicted in Fig. 4 that is able to solve any given instance of Subset Sum in a constant number of steps.

Consider the following instance of Subset Sum to be solved: \(V = (\{v_1,v_2,\ldots ,v_n\}, S).\) In the initial configuration, the leftmost neurons contain (starting from the top to bottom) \(v_1,v_2,\ldots ,v_n\) spikes, while the rightmost neurons do not contain spikes.

When the computation starts, each leftmost neuron non-deterministically applies one of its rules, thus including or not the corresponding value \(v_i\) in the (candidate) solution \(B \subseteq V\). The spikes emitted by all neurons applying a firing rule are collected in the rightmost neurons (let us denote by N the total amount of spikes collected).

We have now three possible cases:The given instance of Subset Sum has a positive answer if and only if a single spike is emitted during the computation.

As pointed out in Leporati et al. (2007), a problem related to the SN P system described above is that the rules of the neurons are checking for the existence of a number of spikes which may be of an exponential size with respect to the usually agreed instance size of Subset Sum. Moreover, the system may require, to be initialized, a number of spikes which could also be exponential.

Nonetheless, in the same paper it was shown that the numbers occurring in the instance of Subset Sum in input, namely \(v_1, v_2,\ldots , v_n\), can be also inserted in the system in binary form, and a Spiking Neural P sub-system is able to convert such binary encoding in a unary encoding in polynomial time. In this way, it was proved that the possibility to efficiently solve Subset Sum by means of an SN P system like the one described before does not require an exponential effort to initialize the system, but depends only on the non-deterministic application of the rules.

A question that arises immediately concerns the possibility to obtain similar results by deterministic systems, possibly by considering added features to increase their efficiency. In many variants of standard P systems, an interesting feature that is commonly considered to improve efficiency of deterministic systems is the possibility to give an active role to membranes. In particular, P systems with active membranes are able to create new membranes during the computation by division, budding, or separation of existing membranes, allowing in this way to obtain a trade off between time and space resources that allows to attack NP–complete (or even harder) problems in polynomial time and exponential space (see, e.g., Păun (2001), Krishna and Rama (1999), Sosík (2019), Zandron et al. (2000)).

Concerning SN P systems, it is known that their ability to evaluate in a constant time the applicability of the rules, according to the associated regular expressions, can be exploited to deterministically solve computationally hard problems in polynomial time. In fact, in Leporati et al. (2009) it was proved that, by using regular expressions in a succinct form over a singleton alphabet, the membership problem is equivalent to NP-complete problems like Subset Sum. In the same paper, it was also proved that when we consider regular expressions of a certain restricted form, then it is possible to simulate SN P systems by a deterministic Turing machine with a polynomial slowdown.

As a consequence, in order to get enough computational power to solve, in polynomial time, computationally hard problems, we could either use complex regular expressions, or we need to consider ideas similar to those exploited for standard P systems, that allow to produce an exponential space in a polynomial number of steps.

A first solution of this type for SN P systems was considered in Pan et al. (2011), where neuron division and budding was allowed (operations inspired from recent discoveries concerning the neural stem cells). By means of these types of rules, a parent neuron can be replaced by two offsprings. In case of neuron division, both the new neurons have the same synapses connections (both coming-in and going-out) as the parent neuron. When a neuron budding rule is applied, instead, one of the two neurons inherits the coming-in synapses connection of the parent neuron, while the other inherits its going-out synapses. Moreover, a synapse from the first to the second new neuron is created.

It was proved that uniform families of SN P systems of this type are able to solve the NP-complete problem SAT in polynomial time (Leporati et al. 2009). An improved solution, obtained by also considering the possibility to dissolve neurons when they are no more necessary to the computation, was proposed in Zhao et al. (2016). In Wang et al. (2010) authors proved that budding of neurons is not strictly necessary: a uniform family of SN P systems with neuron division only can solve the SAT problem in a polynomial number of steps. The system proposed has another very interesting feature: the initial size of the system is limited to a constant number of neurons, differently from the original solution, where a number of neurons that is linear with respect to the dimension of the input SAT formula is required.

Another possibility that has been considered to approach complex problems within the framework of SN P systems was to use pre-computed resources, as proposed in Chen et al. (2006). Instances of a decision problem were encoded in a number of spikes, and then placed, at the beginning of the computation, in an (arbitrarily large) pre-computed system, that has an exponentially large workspace available, in the form of an exponentially large number of inactive neurons, which will be activated and used in constant time in our computation. A constant-time solution for the problem SAT was described in Chen et al. (2006). The assumption of pre-computed resources was used in Ishdorj and Leporati (2008) to build uniform families of spiking neural P systems that solve in deterministic polynomial time instances of the problems SAT and 3-SAT. Similarly, in Ishdorj et al. (2010) solutions for the PSPACE-complete problems QSAT and Q3SAT in polynomial time were proposed, showing in this way that problems in the class PSPACE can be efficiently solved by SN P systems.

In the above sections, we have presented the basic ideas and the main theoretical results concerning Spiking Neural P systems, and only a few of the many variants that have been proposed since the first definition of standard SN P systems in Ionescu et al. (2006). Other variants, trying to incorporate in the computational model different aspects suggested by the biological background, include: SN P systems with anti-spikes, that have an inhibitory function, introduced in Pan and Păun (2009), and in a slightly different form in Song et al. (2012); SN P systems with polarizations (Wu et al. 2018); axon P systems (Zhang et al. 2015), proved to be universal as both function computing devices and number generator devices; SN P systems with communication on request (Pan et al. 2017); and many other variants, variants of the variants and combinations of different features.

The main theoretical issues to be investigated are the same for all these variants. The first question concerns the optimal combination of features and of values of different parameters, needed to obtain computationally complete systems, able to generate/accept recursively enumerable sets of numbers, or to compute recursive functions. This implies the definition of normal forms, the study of the trade-off between different parameters, while maintaining the same computational power, the search for minimal universal systems, the study of relations with other standard and non-standard computing models. In the same vein, various limits and restrictions to the definition of the basic model have been considered, aiming at the definition of variants that are not Turing universal. This would allow to define specific computational classes, possibly having some peculiar decidable properties. The computational power of SN P systems as language generators or acceptors has also been deeply investigated.

Another relevant research direction concerns the efficiency of SN P systems in solving computationally hard problems, such as NP-complete or PSPACE-complete problems. In this respect, there are some intriguing points, concerning unary representations vs binary representations, use of pre-computed resources, uniform solutions vs non-uniform or semi-uniform solutions, which are worthy of further study. An interesting research topic is also to study what restrictions can be considered to obtain systems characterizing specific complexity classes between NP and PSPACE.

In this paper we focussed on theoretical aspects and results, but, of course, the use of these computation models in solving problems related to real-life applications is a topic of great interest: function approximation, pattern recognition, fault diagnosis of power systems, computational biology, biochip design, vehicle routing, cryptography, clustering, or decision making are all possible applications of the model. A recent survey can be found in Fan et al. (2020).