Time-free spiking neural P systems

Different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, a realistic definition of nonsynchronized spiking neural P systems (SN P systems, for short) is considered: during the work of an SN P system, the execution times of spiking rules cannot be known exactly (i.e., they are arbitrary). In order to establish robust systems against the environmental factors, a special class of SN P systems, called time-free SN P systems, is introduced, which always produce the same computation result independent of the execution times of the rules. The universality of time-free SN P systems is investigated. It is proved that these P systems with extended rules (several spikes can be produced by a rule) are equivalent to register machines. However, if the number of spikes present in the system is bounded, then the power of time-free SN P systems falls, and in this case, a characterization of semilinear sets of natural numbers is obtained.     

On spiking neural P systems

This work deals with several aspects concerning the formal verification of SN P systems and the computing power of some variants. A methodology based on the information given by the transition diagram associated with an SN P system is presented. The analysis of the diagram cycles codifies invariants formulae which enable us to establish the soundness and completeness of the system with respect to the problem it tries to resolve. We also study the universality of asynchronous and sequential SN P systems and the capability these models have to generate certain classes of languages. Further, by making a slight modification to the standard SN P systems, we introduce a new variant of SN P systems with a special I/O mode, called SN P modules, and study their computing power. It is demonstrated that, as string language acceptors and transducers, SN P modules can simulate several types of computing devices such as finite automata, a-finite transducers, and systolic trellis automata.     

Reversible spiking neural P systems

Spiking neural (SN) P systems are a class of distributed parallel computing devices inspired by the way neurons communicate by means of spikes. In this work, we investigate reversibility in SN P systems, as well as the computing power of reversible SN P systems. Reversible SN P systems are proved to have Turing creativity, that is, they can compute any recursively enumerable set of non-negative integers by simulating universal reversible register machine.     

Asynchronous spiking neural P systems

We consider here spiking neural P systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete.For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable.     

Homogenous spiking neural P systems with anti-spikes

Spiking neural P systems with anti-spikes (ASN P systems, for short) are a class of neural-like computing models in membrane computing, which are inspired by neurons communication through both excitatory and inhibitory impulses (spikes). In this work, we consider a restricted variant of ASN P systems, called homogeneous ASN P systems, where any neuron has the same set of spiking and forgetting rules. As a result, we prove that such systems can achieve Turing completeness. Specifically, it is proved that two categories of pure form of spiking rules (for a spiking rule, if the language corresponding to the regular expression that controls its application is exactly the form of spikes consumed by the rule, then the rule is called pure) are sufficient to compute and accept the family of sets of Turing computable natural numbers.     

通用的不带延迟的同质脉冲神经膜系统

脉冲神经膜系统是一种膜系统中吸收了脉冲神经网络特点的新型生物计算装置,具有强大的计算能力。同质脉冲神经膜系统是指一种所有神经元具有相同规则集合的脉冲神经膜系统的变体。研究了突触上带权值和突触上不带权值的两种同质脉冲神经膜系统在不使用具有延迟的激发规则情况下的计算通用性问题,并证明了这两种不带延迟的同质脉冲神经膜系统无论是工作在产生模式下,还是工作在接收模式下都是计算通用的。解决了曾湘祥、张兴义和潘林强提出的关于不带延迟的同质脉冲神经膜系统是否具有计算通用性的公开问题。     

Characterizations of some classes of spiking neural P systems

We look at the recently introduced neural-like systems, called SN P systems. These systems incorporate the ideas of spiking neurons into membrane computing. We study various classes and characterize their computing power and complexity. In particular, we analyze asynchronous and sequential SN P systems and present some conditions under which they become (non-)universal. The non-universal variants are characterized by monotonic counter machines and partially blind counter machines and, hence, have many decidable properties. We also investigate the language-generating capability of SN P systems.     

On the computational complexity of spiking neural P systems

It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent of the input length. Following this, we construct a universal spiking neural P system with exhaustive use of rules that simulates Turing machines in linear time and has only 10 neurons.     

Notes on spiking neural P systems and finite automata

Spiking neural P systems (in short, SN P systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SN P systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. A variant known as SN P modules generalize SN P systems by using extended rules (more than one spike can be emitted each step) and a set of input and output neurons. In this work we continue relating SN P modules and finite automata. In particular, we amend and improve previous constructions for the simulatons of deterministic finite automata and state transducers. Our improvements reduce the number of neurons from three down to one, so our results are optimal. We also simulate finite automata with output, and we use these simulations to generate automatic sequences.     

On languages generated by asynchronous spiking neural P systems

In this paper, we investigate the languages generated by asynchronous spiking neural P systems. Characterizations of finite languages and recursively enumerable languages are obtained by asynchronous spiking neural P systems with extended rules. The relationships of the languages generated by asynchronous spiking neural P systems with regular and non-semilinear languages are also investigated.     

Small universal simple spiking neural P systems with weights

Spiking neural P systems with weights（WSN P systems,for short） are a new variant of spiking neural P systems,where the rules of a neuron are enabled when the potential of that neuron equals a given value.It is known that WSN P systems are universal by simulating register machines. However,in these universal systems,no bound is considered on the number of neurons and rules. In this work,a restricted variant of WSN P systems is considered,called simple WSN P systems,where each neuron has only one rule. The complexity parameter,the number of neurons,to construct a universal simple WSN P system is investigated. It is proved that there is a universal simple WSN P system with 48 neurons for computing functions; as generator of sets of numbers,there is an almost simple（that is,each neuron has only one rule except that one neuron has two rules） and universal WSN P system with 45 neurons.     

Experiments on the reliability of stochastic spiking neural P systems

In the area of membrane computing, time-freeness has been defined as the ability for a timed membrane system to produce always the same result, independently of the execution times associated to the rules. In this paper, we use a similar idea in the framework of spiking neural P systems, a model inspired by the structure and the functioning of neural cells. In particular, we introduce stochastic spiking neural P systems where the time of firing for an enabled spiking rule is probabilistically chosen and we investigate when, and how, these probabilities can influence the ability of the systems to simulate, in a reliable way, universal machines, such as register machines.     

On spiking neural P systems and partially blind counter machines

A k-output spiking neural P system (SNP) with output neurons, , generates a tuple of positive integers if, starting from the initial configuration, there is a sequence of steps such that during the computation, each O _i generates exactly two spikes aa (the times the pair aa are generated may be different for different output neurons) and the time interval between the first a and the second a is n _i . After the output neurons generate their pairs of spikes, the system eventually halts. We give characterizations of sets definable by partially blind multicounter machines in terms of k-output SNPs operating in a sequential mode. Slight variations of the models make them universal.     

On the power of elementary features in spiking neural P systems

Since their first publication in 2006, spiking neural (SN) P systems have already attracted the attention of a lot of researchers. This might be owing to the fact that this abstract computing device follows basic principles known from spiking neural nets, but its implementation is discrete, using membrane computing background. Among the elementary properties which confer SN P systems their computational power one can count the unbounded fan-in (indegree) and fan-out (outdegree) of each “neuron”, synchronicity of the whole system, the possibility of delaying and/or removing spikes in neurons, the capability of evaluating arbitrary regular expressions in neurons in constant time and some others. In this paper we focus on the power of these elementary features. Particularly, we study the power of the model when some of these features are disabled. Rather surprisingly, even very restricted SN P systems keep their universal computational power. Certain important questions regarding this topic still remain open.     

Compositional semantics and behavioral equivalences for P Systems

The aim of the paper is to give a compositional semantics in the style of the Structural Operational Semantics (SOS) and to study behavioral equivalence notions for P Systems. Firstly, we consider P Systems with maximal parallelism and without priorities. We define a process algebra, called P Algebra, whose terms model membranes, we equip the algebra with a Labeled Transition System (LTS) obtained through SOS transition rules, and we study how some equivalence notions defined over the LTS model apply in our case. Then, we consider P Systems with priorities and extend the introduced framework to deal with them. We prove that our compositional semantics reflects correctly maximal parallelism and priorities.     

Adaptive fuzzy spiking neural P systems for fuzzy inference and learning

Fuzzy spiking neural P systems (in short, FSN P systems) are a novel class of distributed parallel computing models, which can model fuzzy production rules and apply their dynamic firing mechanism to achieve fuzzy reasoning. However, these systems lack adaptive/learning ability. Addressing this problem, a class of FSN P systems are proposed by introducing some new features, called adaptive fuzzy spiking neural P systems (in short, AFSN P systems). AFSN P systems not only can model weighted fuzzy production rules in fuzzy knowledge base but also can perform dynamically fuzzy reasoning. It is important to note that AFSN P systems have learning ability like neural networks. Based on neuron's firing mechanisms, a fuzzy reasoning algorithm and a learning algorithm are developed. Moreover, an example is included to illustrate the learning ability of AFSN P systems.     

Uniform solutions to SAT and Subset Sum by spiking neural P systems

We continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: Subset Sum{\tt Subset}\,{\tt Sum} and SAT.{\tt SAT}. For both of them we provide uniform constructions of standard spiking neural P systems (i.e., not using extended rules or parallel use of rules) which solve these problems in a constant number of steps, working in a non-deterministic way. This improves known results of this type where the construction was non-uniform, and/or was using various ingredients added to the initial definition of spiking neural P systems (the SN P systems as defined initially are called here “standard”). However, in the Subset Sum{\tt Subset}\,{\tt Sum} case, a price to pay for this improvement is that the solution is obtained either in a time which depends on the value of the numbers involved in the problem, or by using a system whose size depends on the same values, or again by using complicated regular expressions. A uniform solution to 3-SAT{\tt SAT} is also provided, that works in constant time.     

A computational approach for nuclear export signals identification using spiking neural P systems

Nuclear export signal (NES) is a nuclear targeting signal within cargo proteins, which is involved in signal transduction and cell cycle regulation. NES is believed to be “born to be weak”; hence, it is a challenge in computational biology to identify it from high-throughput data of amino acid sequences. This work endeavors to tackle the challenge by proposing a computational approach to identifying NES using spiking neural P (SN P) systems. Specifically, secondary structure elements of 30 experimentally verified NES are randomly selected for training an SN P system, and then 1224 amino acid sequences (containing 1015 regular amino acid sequences and 209 experimentally verified NES) abstracted from 221 NES-containing protein sequences randomly in NESdb are selected to test our method. Experimental results show that our method achieves a precision rate 75.41 %, better than NES-REBS 47.2 %, Wregex 25.4 %, ELM, and NetNES 37.4 %. The results of this study are promising in terms of the fact that it is the first feasible attempt to use SN P systems in computational biology after many theoretical advancements.

     

On string languages generated by spiking neural P systems with exhaustive use of rules

We continue the study of (extended) spiking neural P systems with exhaustive use of rules by considering these computing devices as language generators. Specifically, a step is associated with a symbol according to the number of spikes emitted by the output neuron and the sequence of these symbols associated with a halting computation constitutes a string. Two cases are considered: one of them interprets a step when no spike is emitted as a specified symbol, the other interprets such a step as the empty string. In both cases, it is proved that finite and recursively enumerable languages are characterized by extended spiking neural P systems working in the exhaustive mode. The relationships with regular languages are also investigated.