Research On The Computational Power Of Spiking Neural P Systems

If the linewidth of silicon-based microelectronic devices would develop to be less than 10nm, then it would be difficult to overcome the obstacles which are caused by the constraints of devices in working principle, technology, manufacturing cost, and so on. Nowadays, a frontier and hot issue in the field of computer science is to break through the framework of silicon-based devices, and to develop new technologies of non-tradition. Membrane computing is one of the research fields of unconventional computing. Membrane systems, currently also called P systems, are a class of distributed parallel computing models, which are abstracted from the way living cells, tissue, organs, or other structures process chemical compounds. Since it has been shown that they have powerful computational capability and significant potential to be applied in linguistics as well as computer graphics, systems biology, combinational optimization, and so on, this area has received much attraction from the scientific community. In this dissertation, we shall investigate a special class of P systems, called spiking neural P systems (SN P systems for short), which are inspired from the biological phenomena that in the brain the neurons cooperate to deal with spikes by axons. From the three aspects of language (or numbers) generating power, small universality and computational efficiency, the computational power of spiking neural P systems is investigated in this dissertation. The detailed contents are as follows:Firstly, the language (or numbers) generating power of spiking neural P systems is investigated. One of the central problems on investigating the computational power of computing devices is to consider their language (or numbers) generative power. In this dissertation, we investigate the language (or numbers) generating power of three specific classes of spiking neural P systems, that is, spiking neural P systems with exhaustive use of rules, asynchronous spiking neural P systems and axon P systems.For spiking neural P systems with exhaustive use of rules, under the definitions of restricted language and non-restricted language, their language generative power are investigated respectively when extended rules are used. 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. Since under the non-synchronized mode the time does not matter, we can only consider the non-restricted language in asynchronous spiking neural P systems. Under this definition, the language generative power of asynchronous spiking neural P systems is investigated when extended rules are used. Characterizations of finite 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. Moreover, the generative power of axon P systems is investigated when they are used as number generators and language generators, respectively. As numbers generators, we obtain the relationships of sets of numbers generated by axon P systems with finite and semilinear sets of numbers; as language generators, we obtain the relationships of the languages generated by axon P systems with finite and context-free languages.Then we investigate the small universality of spiking neural P systems. One of the classic problems in computer science is to investigate the small universality of computing models. For spiking neural P systems, besides in computer science, it is also interesting in biology to investigate its small universality: a measure method of small universal 'brain' is given. In this dissertation, the small universality of spiking neural P systems is investigated as follows:Based on the small universal spiking neural P systems constructed by A. P(?)un et. al, the problem of how to optimize the number of their neurons is addressed. To this aim, the idea is proposed that two ADD modules, two SUB modules, and an ADD module and a SUB module can share the auxiliary neurons in some cases. By checking the various cases in which two modules associated with any two instructions can share auxiliary neurons, the instructions of the small universal register machine can be classified into several groups, such that all modules associated with the instructions in each group can share auxiliary neurons. In this way, a small universal spiking neural P systems with smaller number of neurons is obtained. Moreover, under both cases in which they are used as devices computing functions and as devices generating sets of numbers, small universal spiking neural P systems with exhaustive use of rules are constructed, respectively. By considering the cases in which auxiliary neurons are shared, the number of neurons used by them is optimized.Finally, the computational efficiency of spiking neural P systems is investigated. Since the topological structure of spiking neural P systems is fixed, the workspace cannot be generated during the computation by such systems themselves, and thus trading space for time cannot be realized. In this dissertation, the computational efficiency of spiking neural P systems is investigated, under the assumption that some pre-computed resources of exponential size (i.e., the number of neurons used by the system is exponential) are given in advance. Using this kind of systems, a family of spiking neural P systems is constructed which can solve QSAT, a PSPACE-complete problem. In this family of spiking neural P systems, each system can uniformly solve all instances of QSAT of a fixed size in a polynomial time with respect to the size of the problem.