Dissertation > Excellent graduate degree dissertation topics show

Research on the Computational Power of P Systems with Network Structure

Author: JiangZuo
Tutor: PanLinQiang
School: Huazhong University of Science and Technology
Course: System Analysis and Integration
Keywords: Membrane computing Membrane system P system with network structure Computational universality Computational efficiency
CLC: TP399-C8
Type: PhD thesis
Year: 2011
Downloads: 61
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Expression Evaluation by Cell-like Model,TP38
  2. Particle Swarm Optimization Membrane Algorithm and Its Application Research,TP18
  3. Research on Signed Numbers Arithmetic Operations with Membrane Computing,TP301
  4. Arithmetic Operation by Biological Technology,TP301.6
  5. A Study of Endoplasmic Reticulum Inspired Membrane Computing Optimization Algorithms,TP301.6
  6. The Research of Neuron-like and Cell-like P Systems for Application,TP338.6
  7. Research on Spiking Neural P Systems with a Minimal Parallelism of Using of Rule,TP18
  8. Quantum-Inspired Evolutionary Membrane Computing for Emitter Signals,TN911.6
  9. Design of S-boxes Optimum Alogrithms,TP301.6
  10. Film Optimization in the application of DNA coding,Q75
  11. The Improvement of Spiking Neuron P Systems and the Foundation of Automata Model,TP301.1
  12. Formal Modeling and Simulation of Biological Process,TP391.9
  13. Research on Membrane Computing Optimization Methods for Control System Design,TP273.5
  14. Research on Bio-inspired Optimization Algorithms Based on Membrane Computing and Applications,TP301.6
  15. Spiking neural computing performance of the system,TP38
  16. Research on the Computational Power of Spiking Neural P Systems,TN401
  17. Performance of the Models and Algorithms in the Image Reconstruction of Diffuse Optical Tomography,TN215
  18. The Study on Effect of Exogenous Substances on Chilling Sreess Tomato Seedling Phusiological Indexs and Membrane System,S641.2
  19. Municipal solid waste management information system development,TU993
  20. Splitting desert xeric shrubs grown morphogenesis and adaptation mechanisms Comparative Study,Q944

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > In other aspects of the application
© 2012 www.DissertationTopic.Net  Mobile