Computational Power of Spiking Neural P Systems

Following the fundamentals of spiking neural P systems (for short, SNP systems), one of the important research topic is to examine their computational power in relation to classical models of computation. This chapter first shows that the computational completeness can be obtained for SNP systems of the basic form, but also for their restricted forms with restrictions on the removal of delays and/or forgetting rules, the form of the regular expressions used in the spiking rules, and the outdegree of the synapse graph, as well as for the systems under extended form of the rules and different derivation modes for the application of the rules. Moreover, the number of neurons needed for constructing universal SNP systems is optimized by introducing mathematical strategies and additional features, and several small universal SNP systems are obtained. Then, three classes of non-computationally complete SNP systems are analyzed and some restrictions under which they become not computationally complete are presented. Finally, the computational power of SNP systems as string language generators with respect to the families of languages in the Chomsky hierarchy is investigated.