Study On Computational Property Of Timed Membrane Systems And Its Applications

Membrane systems which are called P systems are a class of distributed parallel computing model.Inspired by the structure and function of individual cells,tissues and organs,the basic model of the membrane computing is proposed.Many research results has proved that the computational power of many membrane systems is equivalent to that of Turing machines.Theoretically,P systems can be used as an ideal computing machine.It is assumed that each rule can be completed in exactly one unit time in a standard P system.However,the execution time of different biochemical reactions is often influenced by a variety of factors so that its execution time is hard to control.Inspired by this biological motivation,this paper mainly investigates the computational power,computational effectiveness and computational efficiency of P systems in a time-free way.Some better computing systems with fault tolerance are constructed by expanding the range of existing timed P systems.In addition,enlightened by some biometrics and biological phenomena,two variants of P systems,timed P systems with active membranes using promoters and homeostasis tissue P systems with object evolutional rules,is proposed to construct more efficient timed P systems.At last,inspired by some features of P systems,a new algorithm based on classification noises detection is proposed.The main research work of this dissertation is described as follows:(1)A new variant of timed P systems with active membranes was proposed,where the application of rules is regulated by promoters with only two polarizations.Two solutions to the SAT problem are constructed in the framework of such recognizer timed P systems in polynomial time.One is semi-uniform,while the other is uniform.For the two solutions,execution time of rules has no influence on the computation results.At last,it is proved that any Turing computable set of numbers can be generated by such a P system.Compared with the existing methods,the systems constructed in our work require fewer necessary resources and RS-steps,which show that these solutions are effective to NP-complete problems.(2)Considering cell-like timed P systems with proteins,a uniform solution to the SAT problem is constructed in the framework of recognizer timed P systems in the polynomial time.For this method,we only apply division rules with elementary membranes,and prove that such system is shown to be highly effective for NP-complete problem even in a time-free manner with communication rules of the length at most 4.Moreover,we consider flip-flop P systems with proteins,and introduce the time-free method into such system.Based on the model,we construct a uniform solution to the SAT problem in the framework of recognizer timed P systems in the polynomial time.(3)Considering tissue P systems,a uniform and efficient solution to the SAT problem is constructed in a time-free way.As a result,we prove that such system is shown to be highly effective for NP-complete problem even in a time-free manner with communication rules of the length at most 3.The feasibility and effectiveness of the proposed system is demonstrated by an instance.(4)A new variant of tissue P systems is proposed,called homeostasis tissue P systems with object evolutional rules,where there are no infinitely many objects in the environment.We construct two uniform solutions in the framework of such recognizer P systems in linear time.One solution is constructed to solve the SAT problem with communication rules of the length at most 2,and the other solution is constructed to solve the 3-coloring problem in a time-free way.Moreover,we prove that any Turing computable set of numbers can be generated by such a P system.(5)Motivated by the basic idea of active membrane P systems and evolutionary rules,a new algorithm based on classification noises detection is proposed.On the one hand,cross validation in the training process is avoided so that it has high efficiency and stability.On the other hand,more support vectors can be reserved by iterative training in the membranes and verifying the KKT condition so that it can get better generalizability.The experimental results show that the performance of SVM is effectively improved.The results show that the execution time of the involved rules has no influence on the correctness of the solution,which reflects the robustness of the biological system from the computational point of view.In our work,the constructed P systems have high computational efficiency to solve the NP-complete problems even in a time-free manner.In addition,the proposed classification algorithm solves the problem that the existing chunking algorithms may discard too many support vectors,which enables it to achieve higher average accuracy.