Research On The Computational Power Of P Systems With Network Structure

Since the continuous development of science, the current research always involves sev-eral different disciplines, and it's a trend to break down the boundary of the classical disci-plines and do cross-disciplinary research. In the field of computer science, biology always has a significant impact on its development. Biological system is a complex "computing system", and many computing ideas, models and methods are inspired from it, such as evolutionary computing and neural network, which belong to the emerging area of natural computing.Membrane computing, initiated by Paun in 1998, is a new branch of natural computing, and this cross-disciplinary research involved in computer science, biology and mathematics aims to abstract computing ideas and models from the structure and the functioning of living cells, as well as from the way the cells are organized in tissues or higher order structure. The resulting models are called membrane systems, or P systems, due to the contribution of Paun. Now membrane computing is a very active research field, for it introduces into computer science new method and technology of distributed and parallel processing, and provides new tools for modeling and simulation of biological systems.There are two kinds of membrane structure in P systems, that is, hierarchy structure and network structure. This dissertation deals with P systems with network structure, including tissue P systems and spiking neural P systems (SN P systems for short). Tissue P systems are inspired from the biochemical reality that in tissues the cells communicate (chemicals, energy, information) with each other by means of complex network of protein channel. Spiking neural P systems are inspired from the biological phenomena that in the brain the neurons cooperate through processing impulses in the complex net established by synapses.From the three aspects of language generating power(or number recognizing power), small universality and computational efficiency, the computational power of P systems with network structure is investigated in this dissertation. The detailed contents are as follows:One of the central problems on investigating the computational power of computing devices is to consider their language (or numbers) generative (or recognizing) power. This work investigates the binary string language generating power of spiking neural P systems with exhaustive use of rules, and the number recognizing power of tissue P systems working in look-ahead mode. For spiking neural P systems with exhaustive use of rules, their binary string language generative power are investigated when extended rules are used. Moreover, the power of tissue P systems working in look-ahead mode is investigated when they are used as number acceptors. Characterizations of recursively enumerable languages are obtained by tissue. P systems under the look-ahead mode.Looking for small universal computing devices is a natural and well investigated topic in computer science. For spiking neural P systems, besides in computer science, small universality is also interesting in biology:a measure method of small universal "brain" is given. This dissertation investigates the small universality of spiking neural P systems with anti-spikes. Under both cases in which anti-spikes are produced by rules and by inhibitory synapses, small universal spiking neural P systems are constructed, and the number of neu-rons used by them is optimized by considering the cases in which auxiliary neurons are shared.Finally, the computational efficiency of tissue P systems is investigated. A family of tissue P systems with cell separation is constructed which can solve Subset Sum, an NP-complete problem. In this family, each system can uniformly solve all instances of Subset Sum of a fixed size in a polynomial time with respect to the size of the problem. Moreover, tissue P systems working in look-ahead mode are constructed which can solve 3-coloring. The tissue P systems constructed can solve all instance of 3-coloring with fixed number of nodes in a linear time with respect to the number of nodes. These results verify that cell separation is an effective method of space-time trade-off, and look-ahead mode helps to decrease the inherent non-determinism of P systems.