摘要
经过近几十年的发展,人们希望第四代计算机(即超大规模集成电路计算机)具有更多的类似人的智能,于是开始寻找第五代的计算机来取代它们,例如：生物计算机,量子计算机等。其中膜计算是生物计算的重要分支,它通过模拟细胞及其组织的结构与功能,构造出具有分布式结构的并行计算模型。我们研究的是其中一种网状膜系统,即脉冲神经膜系统。这种膜计算模型源自于生物神经系统中神经元通过突触传递脉冲交换信息的机制。本文通过结合形式语言和自动机理论,从语言的产生能力、计算通用性和有效性以及数的识别能力几方面,对多种具有其它生物特性的脉冲神经膜系统进行了研究,主要工作如下：
针对神经元周围的星状神经胶质细胞可以对神经元间的相互左右产生重要影响的现象,本文建立了一种具有星细胞的脉冲神经膜系统。通过模拟注册机,证明了在同步模式下,该系统可实现计算通用性。如果我们限制系统中每个神经元中的脉冲数目,那么该系统可以刻画自然数的半线性集合。另外在异步工作模式下,这种神经元和星细胞结合起来的新系统也是等价于图灵机的。这些结果表明,尽管神经元很简单,但是它组成的网络却可以具有很强的计算能力。
针对Ibarra等人提出的,使用标准规则的异步脉冲神经膜系统是否具有通用性的公开问题,本文提出了一种具有激发时限的异步模式,在此模式下,所有的激发规则都具有同一个激发时限,我们通过模拟注册机,证明了使用标准规则的脉冲神经膜系统可以达到计算通用性,解决了公开问题。
在经典的脉冲神经膜系统中,判断一条激发规则的使用与否,有时可能是NP困难的,这在某种程度上也不符合生物神经系统的现实。本文引入细胞膜电势来代替脉冲值,建立了一种新的规则判断方式,避免了大量的计算损耗。另外用有理数取代自然数来表示各种参数,使系统可以处理跟有理数有关的问题,提升了系统的功能与计算能力,扩大了解决问题的范围。通过模拟注册机,我们证明了这种带权值的脉冲神经膜系统可以实现计算通用性,并能求解计算困难问题。该系统使用自然数来表示各种参数时,只能刻画数字的半线性集合。
针对脉冲神经膜系统的计算效率问题,我们分别使用生物里面神经元分裂和芽殖的特性创建了两种新的系统,来生成所需的计算空间,从而实现空间换时间。本文证明这两种系统可求解著名的NP完全问题,可以在多项式时间内求解给定规模的NP完全问题的所有算例。
After decades of development, people wish the fourth generation computer, namely, massive scale integrated circuit computer would possess more intelligence that resembles human intelligence. Thus they commence seeking to replace them with the fifth generation computers, namely, biological computers and quantum computers. As for biological com-puters, membrane computing is one of the important branches in the field of bio-computing. It constructs paralleled computation models of distribution structure by simulating the struc-tures and functions of cells and their tissues. Our research has explored one type of the membrane systems, namely spiking neural membrane systems. These systems are inspired by the biological mechanism, with which the neurons in the brain cooperate through pro-cessing impulses in the complex net established by synapses. This dissertation has investi-gated a number of different variants of the spiking neural membrane systems in the aspect of language generating power, commotional university and efficiency and number recognizing power. The main research work are as follows:
This dissertation created a new variant of spiking neural membrane systems with astro-cyte, inspired by the biological phenomenon that the astrocyte around neurons have signif-icant impact on the communication between neurons. Through simulating Turing machine, it is proved that these systems are Turing universal in synchronous working mode. The sys-tems could generate semi-linear set of natural numbers if we restrict the number of spikes in each neuron. Moreover, these new systems combined by neurons and astrocytes are also Turing universal when they work in asynchronous mode. All those research results demon-strate that the network constructed by the simple neurons has great computational power.
Furthermore, in this dissertation we create the time bounded asynchronous model to solve the open problem introduced by Ibarra, that whether the spiking neural membrane systems with standard rules are Turing complete. In this model, all the spiking rules have the same bounded time. By simulating register machine, we proved that using the model we created, spiking neural systems could calculate any set of Turing computable numbers as the number generators.
In standard spiking neural membrane systems, there is a potential NP-complete prob-lem to determine whether a spiking rule can be applied or not. It is also not in accordance with biological facts in biological neural networks. This dissertation established a new de-termine method by introducing membrane potential to replace spikes, and real number to replace natural number, into the systems. It saves large amount of computing time, enables the system to handle problems related to rational numbers, improves the system functions and computing power, and extends scope of problems that it could solve. By simulating register machine, we proved that spiking neural membrane systems are computationally completed and solve computing difficulty problems. In these systems, if we use natural numbers instead of integers, the systems can only characterize semi-linear set of numbers.
We construct another two new systems respectively using the features of budding rules and neuron division, to generate the needed computational space, subsequently transform the space in to time, solving the problem of low computational efficiency of spiking neural membrane systems. This dissertation proved that these two systems can solve all instances of NP-complete problem in a polynomial time.
引文
[1]Paun Gh. Computing with membranes. Journal of Computer and System Sciences,2000, 61(l):108-143.
[2]Paun Gh, Rozenberg G. A guide to membrane computing. Theoretical Computer Science,2002, 287:73-100.
[3]Martin-Vide C, Paun A, Paun Gh. Membrane computing:new results, new problems. Bulletin of the EATCS,2002,78:204-212.
[4]Paun Gh, P6rez-Jimenez M. Membrane computing:brief introduction, recent results and applica-tions. Biosystems,2006,85(1):11-22.
[5]Paun Gh. Membrane computing:power, efficiency, applications. Lecture Notes in Computer Science,2005,3526:396-407.
[6]Ciobanu G, Paun Gh, Perez-Jimenez M, editors. Applications of Membrane Computing. Berlin: Springer-Verlag,2006.
[7]Paun Gh, Pazos J, Perez-Jimenez M, et al. Symport/antiport P systems with three objects are universal. Fundamenta Informaticae,2005,64(1-4):353-367.
[8]Pan L, Martin-Vide C. Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes. Journal of Parallel and Distributed Computing,2005,65(12):1578-1584.
[9]Ji S. The bhopalator:an information/energy dual model of the living cell. Fundamenta Informati-cae,2002,49(1):147-165.
[10]Nishida T. Membrane algorithms. Lecture Notes in Computer Science,2006,3850:55-66.
[11]Alhazov A. Communication in Membrane Systems with Symbol Objects:[PhD Dissertation]. Seville, Spain:University of Seville,2006.
[12]Popa B. Membrane Systems with Limited Parallelism:[PhD Dissertation]. Ruston, USA: Louisiana Tech University,2006.
[13]Sburlan D. Promoting and Inhibiting Contexts in Membrane Computing:[PhD Dissertation]. Seville, Spain:University of Seville,2006.
[14]黄亮.膜计算优化算法研究：[博士学位论文].浙江大学,2007.
[15]张兴义.脉冲神经膜系统的计算能力研究：[博士学位论文].华中科技大学,2009.
[16]Paun Gh, Rozenberg G, Salomaa A, editors. The Oxford Handbook of Membrane Computing. Oxford University Press,2010.
[17]张葛祥,潘林强.自然计算的新分支—膜计算.计算机学报,2010,33(2)：208-214.
[18]Martin-Vide C, Paun Gh, Rozenberg G. Membrane systems with carriers. Theoretical Computer Science,2002,270(1-2):779-796.
[19]Martin-Vide C, Paun Gh, Pazos J, et al. Tissue P systems. Theoretical Computer Science,2003, 296(2):295-326.
[20]Cavaliere M, Genova D. P systems with symport/antiport of rules. Journal of Universal Computer Science,2004,10(5):540-558.
[21]Bernardini F, Gheorghe M. Population P systems. Journal of Universal Computer Science,2004, 10(5):509-539.
[22]Cavaliere M, Sedwards S. Membrane systems with peripheral proteins:transport and evolution. Electronic Notes in Theoretical Computer Science,2007,171(2):37-53.
[23]Paun A, Popa B. P systems with proteins on membranes and membrane division. Lecture Notes in Computer Science,2006,4036:292-303.
[24]Dassow J, Paun Gh. On the power of membrane computing. Journal of Universal Computer Science,1999,5(2):33-49.
[25]Freund R, Paun A. Membrane systems with symport/antiport rules:universality results. Lecture Notes in Computer Science,2003,2957:270-287.
[26]Freund R, Kari L, Oswald M, et al. Computationally universal P systems with priorities:two catalysts are sufficient. Theoretical Computer Science,2005,330(2):251-266.
[27]Sosik P, Freund R. P systems with priorties are computationally universal. Lecture Notes in Computer Science,2003,2597:400-409.
[28]Gutierrez-Naranjo M, Perez-Jimenez M, Romero-Campero F. A uniform solution to SAT using membrane creation. Theoretical Computer Science,2007,371(1-2):54-61.
[29]Sieglemann H, Sontag E. Computing with spikes. Journal of Computer and System Sciences, 1995,50:132-150.
[30]Perea G, Araque A. Communication between astrocytes and neurons:a complex language. Journal of Physiology Paris,2002,96:199-207.
[31]Binder A, Freund R, Oswald M, Vock L. Extended spiking neural P systems with excitatory and inhibitory astrocytes. Proc. Fifth Brainstorming Week on Membrane Computing,2007,63-72.
[32]Volterra A, Meldolesi J. Astrocytes, from brain glue to communication:the revolution continues. Nature Reviews Neuroscience,2005,6:626-640.
[33]Maass W, Bishop C, (Eds.). Pulsed Neural Networks. Cambridge:MIT Press,1999.
[34]Ionescu M, Paun Gh, Yokomori T. Spiking neural P systems. Fundamenta Informaticae,2006, 71:279-308.
[35]Bennett CH. On constructing a molecular computer. IBM Journal of Research and Development, 1973,17:525-532.
[36]Conrad M. On design principles for a molecular computer. Communications of the ACM,1985, 28:464-480.
[37]Leporati A, Mauri G, Zandron C, Paun G, Perez-Jimenez M. Uniform solutions to SAT and Subset Sum by spiking neural P systems. Natural Computing,2009,8:681-702.
[38]Turing A. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society,1937,2:230.
[39]Turing A. Computability and λ-definability. Journal of Symbolic Logic,1937,2:153-163.
[40]Rogozhin Y. Small universal turing machines. Theoretical Computer Science,1996,168:215-240.
[41]Paum Gh. Spiking neural P systems with astrocyte-like control. Journal of Universal Computer Science,2007,13:1707-1721.
[42]Paun G, Perez-Jimenez M. Spiking neural P systems. An overview. Advancing Artificial Intelli-gence through Biological Process Applications,2008,60-73.
[43]Alhazov A, Perez-Jimenez M. Uniform solution of QSAT using polarizationless active mem-branes. Lecture Notes in Computer Science,2007,4664:122-133.
[44]Pan L, Alhazov A, Isdorj T. Further remarks on P systems with active membranes, separation, merging and release rules. Soft Computing,2005,9(9):686-690.
[45]Krishna S, Rama R. Breaking DES using P systems. Theoretical Computer Science,2003,299(1-3):495-508.
[46]Perez-Jimenez M, Romero-Campero F. A study of the robustness of the EGFR signalling cascade using continuous membrane systems. Lecture Notes on Computer Science,2005,3561:268-278.
[47]Manca V, Bianco L. Biological networks in metabolic P systems. BioSystems,2008,91(3):489-498.
[48]Romero-Campero F, Perez-Jim6nez M. Modelling gene expression control using P systems:The lac operon, a case study. BioSystems,2008,91(3):438-457.
[49]Mauri G, Cazzaniga P. Seasonal variance in P system models for metapopulations. Progress in Natural Science,2007,17(4):392-400.
[50]Besozzi D, Cazzaniga P, Pescini D, et al. Modelling metapopulations with stochastic membrane systems. BioSystems,2008,91(3):499-514.
[51]Colomer M, Margalida A, Sanuy D, et al. A bio-inspired computing model as a new tool for model-ing ecosystems:The avian scavengers as a case study. Ecological Modelling,2011,222(1):33-47.
[52]Bel-Enguix G, Gramatovici R. Parsing with active P automata. Lecture Notes in Computer Sci-ence,2004,2933:419-463.
[53]Enguix G. Unstable P systems:applications to linguistics. Lecture Notes in Computer Science, 2005,3365:190-219.
[54]Ceterchi R, Gramatovici R, Jonoska N, et al. Tissue-like P systems with active membranes for picture generation. Fundamenta Informaticae,2003,56(4):311-328.
[55]Nagy B, Szegedi L. Membrane computing and graphical operating systems. Journal of Universal Computer Science,2006,12(9):1312-1331.
[56]Paun Gh, Paun R. Membrane computing as a framework for modeling economic progress, in:Pro-ceedings of Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing,2006,8-11.
[57]Paun Gh, Paun R. Membrane computing and economics:numerical P systems. Fundamenta Informaticae,2006,73(1):213-227.
[58]Nishida T. An approximate algorithm for NP-complete optimization problem exploiting P sys-tems, in:Proceedings of Brainstormming Workshop on Uncertainty in Membrane Computing, 2004,185-192.
[59]Nishida T, Truthe B. Membrane algorithm on Brownian subalgorithm and genetic subalgorithm. International Journal of Foundations of Computer Science,2007,18(6):1353-1360.
[60]Nishida T, Shiotani T, Takahashi Y. Membrane algorithm solving job-shop scheduling problems, in:Proceedings of Ninth Workshop on Membrane Computing, Edinburgh, UK,2008,363-370.
[61]Huang L, Wang N. An optimization algorithm inspired by membrane computing. Lecture Notes in Computer Science,2006,4222:49-52.
[62]Zhang G, Gheorghe M, Wu C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae,2008,87(1):93-116.
[63]Zhang G, Liu C, Gheorghe M. Solving satisfiability problems with membrane algorithms, in: Proceedings of Fourth international conference on BIC-TA,2009,29-36.
[64]曾湘祥.膜优化算法在DNA编码中的应用研究：[硕士学位论文].华中科技大学,2007.
[65]Petreska B, Teuscher C. A reconfigurable hardware membrane system. Lecture Notes in Computer Science,2004,2933:269-285.
[66]Cecilia J, Garcfa J, Guerrero G, et al. Simulating a P system based efficient solution to SAT by using GPUs. Journal of Logic and Algebraic Programming,2010,79(6):317-325.
[67]Canales J, Carrasco J, Hernandez G, et al. Simulation of P systems with active membranes on CUDA. Briefings in Bioinformatics,2010,11(3):313-322.
[68]Paun Gh. Further open problems in membrane computing, in:Proceedings of Second Brainstorm-ing Week on Membrane Computing, Sevilla, Spain,2004.
[69]Paun Gh. Further twenty-six open problems in membrane computing, in:Proceedings of Third Brainstorming Week on Membrane Computing, Sevilla, Spain,2005.
[70]Paun Gh. Tracing some open problems in membrane computing. Romanian Journal of Information Science and Technology,2007,10(4):303-314.
[71]Paun Gh, Perez-Jimenez M. Spiking neural P systems:Recent results, research topic. Springer-Verlag,2009.
[72]Singer S, Nicolson G. The fluid mosaic model of the structure of cell membranes. Science,1972, 175(4023):720-731.
[73]Martin-Vide C, Paun A, Paun Gh. On the power of P systems with symport rules. Journal of Universal Computer Science,2002,8(2):317-331.
[74]Paun Gh, Yu S. On synchronization in P systems. Fundamenta Informaticae,1999,38(4):397-410.
[75]Paun Gh. P systems with active membranes:attacking NP complete problems. Journal of Au-tomata, Languages and Combinatorics,2001,6(1):75-90.
[76]Alhazov A, Pan L, Paun Gh. Trading polarizations for labels in P systems with active membranes. Acta Informatica,2004,41(2):111-144.
[77]Alhazov A, Pan L. Polarizationless P system with active membranes. Grammar,2004,7(1):141-159.
[78]Loewenstein W. The touchstone of life:molecular information, cell communication, and the foundation of life. New York, Oxford:Oxford University Press,1999.
[79]Martin-Vide C, Pazos J, Paun Gh, et al. A new class of symbolic abstract neural nets:tissue P systems. Lecture Notes in Computer Science,2002,2387:290-299.
[80]Martin-Vide C, Pazos J, Paun Gh, et al. Tissue P systems. Theoretical Computer Science,2003, 296(2):295-326.
[81]Freund R, Paun Gh, Perez-Jimenez M. Tissue P systems with channel states. Theoretical Computer Science,2005,330(1):101-116.
[82]Paun Gh, Perez-Jimenez M, Riscos-Nunez A. Tissue P system with cell division. International Journal of Computers, Communications & Control,2008, Ⅲ(3):295-302.
[83]Diaz-Pernil D, Gutierrez-Naranjo M, P6rez-Jimenez M, et al. A linear-time tissue P system based solution for the 3-coloring problem. Electronic Notes in Theoretical Computer Science,2007, 171(2):81-93.
[84]Diaz-Pernil D, Gutierrez-Naranjo M, Perez-Jimenez M, et al. Solving subset sum in linear time by using tissue P system with cell division. Lecture Notes in Computer Science,2007,4527:170-179.
[85]Pan L, P6rez-Jim6nez M. Computational complexity of tissue-like P systems. Journal of Com-plexity,2010,26(3):296-315.
[86]Chen H, Ionescu M, Ishdorj T, Paun A, Paun G, Perez-Jimenez M. Spiking neural P systems with extended rules:universality and languages. Natural Computing,2008,7:147-166.
[87]Diaz-Pernil D, Gutierrez-Naranjo M, Perez-Jimenez M, et al. Efficient simulation of tissue-like P systems by transition cell-like P systems. Natural Computing,2009,8(4):797-806.
[88]Gutierrez-Escudero R, P6rez-Jim6nez M, Rius-Font M. Characterizing tractability by tissue-like P systems, in:Proceedings of Seventh Brainstorming Week on Membrane Computing,2009, 169-180.
[89]Dfaz-Pernil D, Perez-Jimenez M, Riscos-Nunez A. Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology,2008, 11(3):229-241.
[90]Ionescu M, Paun Gh. Spiking neural P systems. Fundamenta Informaticae,2006,71(2-3):279-308.
[91]Paun Gh, Perez-Jimenez M, Salomaa A. Spiking neural P systems:an early survey. International Journal of Foundations of Computer Science,2007,18(3):435-455.
[92]Paun Gh. A quick overview of membrane computing with some details about spiking neural P systems. Frontiers of Computer Science in China,2007, 1(1):37-49.
[93]Paun Gh. Spiking neural P systems. A tutorial. Bulletin of the EATCS,2007,91:145-159.
[94]Paun Gh. Spiking neural P systems, recent results, research topics, in:Proceedings of Algorithmic Bioprocesses,2009,273-291.
[95]Paun Gh. Twenty six research topics about spiking neural P systems, in:Proceedings of Fifth Brainstorming Week on Membrane Computing,2007,263-280.
[96]Chen H, Ionescu M, Ishdorj T. Spiking neural P systems with extended rules:universality and languages. Natural Computing,2008,7(2):147-166.
[97]Chen H, Ionescu M, Paun A, et al. On trace languages generated by spiking neural P systems, in: Proceedings of Eighth International Workshop on Descriptional Complexity of Formal Systems, 2006,94-105.
[98]Paun Gh. Spiking neural P systems used as acceptors and transducers. Lecture Notes in Computer Science,2007,4783:1-4.
[99]Paun Gh. Spiking neural P systems. Power and efficiency. Lecture Notes in Computer Science, 2007,4527:153-169.
[100]Ishdorj T, Leporati A, Pan L. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science,2010,411(25):2345-2358.
[101]Ionescu M, Paun Gh, Yokomori T. Spiking neural P systems with an exhaustive use of rules. International Journal of Unconventional Computing,2007,3(2):135-154.
[102]Cavaliere M, Ibarra O, Paun Gh, et al. Asynchronous spiking neural P systems. Theoretical Computer Science,2009,410(24-25):2352-2364.
[103]Ibarra O, Woodworth S, Yu F, et al. On spiking neural P systems and partially blind counter machine. Lecture Notes in Computer Science,2006,4135:113-129.
[104]Binder A, Freund R, Oswald M, et al. Extended spiking neural P systems with excitatory and inhibitory astrocytes. in:Proceedings of Proc.5th Brainstorming Week on Membrane Computing, Sevilla,2007,63-72.
[105]Chen H, Ishdorj T, Paun Gh. Computing along the axon. Progress in Natural Science,1997, 17(4):417-423.
[106]Cavaliere M, Ibarra O, Paun Gh, Egecioglu O, Ionescu M, Woodworth S. Asynchronous spiking neural P systems. Theoretical Computer Science,2009,410:2352-2364.
[107]Pan L, Paun Gh. Spiking neural P systems with anti-spikes. International Journal of Computers, Communications & Control,2009, IV(3):273-282.
[108]Leporati A, Zandron C, Ferretti C, et al. On the computational power of Spiking neural P systems. International Journal of Unconventional Computing,2009,5(5):459-473.
[109]Freund R, Ionescu M, Oswald M. Extended spiking neural P systems with decaying spikes and/or total spiking, in:Proceedings of International Workshop, Automata for Celluar and Molecular Computing,2007,64-75.
[110]Yuan Z, Zhang Z. Asynchronous spiking neural P systems with promoters. Lecture Notes in Computer Science,2007,4847:693-702.
[111]Ibarra O, Woodworth S. Characterizations of some restricted spiking neural P systems. Lecture Notes in Computer Science,2006,4361:424-442.
[112]Ibarra O, Paun A, Paun Gh, et al. Normal forms for spiking neural P systems. Theoretical Com-puter Science,2007,372(2-3):196-217.
[113]Garcia-Arnau M, Perez D, Rodriguez-Paton A, et al. Spiking neural P systems:stronger normal forms, in:Proceedings of Fifth Brainstorming Week on Membrane Computing,2007,157-178.
[114]Chen H, Ionescu M, Perez-Jimenez M, et al. On string languages generated by spiking neural P systems. Fundamenta Informaticae,2007,75(1-4):141-162.
[115]Ibarra O, Woodworth S. Characterizing regular languages by spiking neural P systems. Interna-tional Journal of Foundations of Computer Science,2007,18(6):1247-1256.
[116]Freund R, Oswald M. Regular (?);—anguages defined by finite extended spiking neural P systems. Fundamenta Informaticae,2008,83(1):65-73.
[117]Chen H, Ishdorj T, Paun Gh, et al. Handling languages with spiking neural P systems with extended rules. Romanian Journal of Information Science and Technology,2006,9(3):151-162.
[118]Cavaliere M, Ibarra O H, Paun Gh, et al. Asynchronous spiking neural P systems:decidability and undecidability. Lecture Notes in Computer Science,2008,4848:246-255.
[119]Ibarra O, Woodworth S. Characterizations of some classes of spiking neural P systems. Natural Computing,2008,7(4):499-517.
[120]Paun A, Paun Gh. Small universal spiking neural P systems. BioSystems,2007,90(l):48-60.
[121]Zhang X, Zeng X, Pan L. Smaller universal spiking neural P systems. Fundamenta Informaticae, 2008,87(1):117-136.
[122]Zhang X, Jiang Y, Pan L. Small universal spiking neural P systems with exhaustive use of rules. Journal of Computational and Theoretical Nanoscience,2010,7(5):890-899.
[123]Neary T. On the computational complexity of spiking neural P systems. Lecture Notes in Com-puter Science,2008,5204:189-205.
[124]Chen H, Ionescu M, Ishdorj T. On the efficiency of spiking neural P systems, in:Proceedings of Eighth International Conference on Electronics, Informaiton, and Communication,2006,49-52.
[125]Ishdorj T, Leporati A. Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources. Natural Computing,2008,7(4):519-534.
[126]Ishdorj T, Leporati A, Pan L, et al. Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science,2010,411(25):2345-2358.
[127]Leporati A, Gutierrez-Naranjo M. Solving Subset Sum by spiking neural P systems with pre-computed resources. Fundamenta Informaticae,2008,87(1):61-77.
[128]Mauri G, Leporati A, Zandron C, et al. Solving numerical NP-complete problems with spiking neural P systems, in:Proceedings of Eighth International Workshop of Membrane Computing, 2007,336-352.
[129]Leporati A, Mauri G, Zandron C, et al. Uniform solutions to SAT and Subset Sum by spiking neural P systems. Natural Computing,2009,8(4):681-702.
[130]Pan L, Paun Gh, Perez-Jimenez M. Spiking neural P systems with neuron division and budding, in:Proceedings of 7th Brainstorming Week on Membrane Computing, Sevilla,2009,151-167.
[131]Wang J, Ishdorj T, Pan L. About the efficiency of spiking neural P systems, in:Proceedings of 7th Brainstorming Week on Membrane Computing, Sevilla,2009,235-251.
[132]Mauri G, Leporati A, Zandron C, Ferretti C. Solving Numerical NP-Complete Problems with Spiking Neural P Systems. Proceeding of 8th International Workshop of Membrane Computing, 2007.
[133]Ishdorj T, Leporati A, Pan L, et al. Solving NP-complete problems by spiking neural P systems with budding rules, in:Proceedings of Tenth Workshop on Membrane Computing, Curtea de Arges,2009,317-336.
[134]Ionescu M, Sburlan D. Some applications of spiking neural P systems. Computing and Informat-ics,2008,27:515-528.
[135]Ceterchi R, Tomescu A. Implementing sorting networks with spiking neural P systems. Funda-menta Informaticae,2008,87(1):35-48.
[136]Gutierrez-Naranjo M, Perez-Jimenez M. A spiking neural P systems based model for Hebbian learning, in:Proceedings of Ninth Workshop on Membrane Computing,2008,189-207.
[137]Metta V, Krithivasan K, Garg D. Modeling spiking neural P systems using timed Petri nets, in: Proceedings of Natrue Biologically Inspired Computing,2009,25-30.
[138]Gutierrez-Naranjo M, Leporati A. First steps towards a CPU made of spiking neural P systems. International Journal of Computers, Commmunications & Control,2009,4(3):244-252.
[139]Ionescu M, Tirnauca C. Dreams and spiking neural P systems. Romanian Journal of Information Science and Technology,2009,12(2):209-217.
[140]Peng H, Wang J. Adaptive spiking neural P systems, in:Proceedings of Sixth International Conference on Natural Computation,2010,3008-3011.
[141]Chomsky N. On certain formal properties of grammars. Information and Control,1959,2(2):137-167.
[142]Linz P. An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers,2000.
[143]Rozenberg G, Salomaa A. Handbook of Formal Languages:Beyond Words. Springer-Verlag, 1997.
[144]冯志伟,孙乐.自然语言处理综述.北京：电子工业出版社,2005.
[145]蒋宗礼,姜守旭.形式语言与自动机理论.北京：清华大学出版社,2003.
[146]Minsky M. Computation:Finite and Infinite Machines. New Jersy:Prentice-Hall,1967.
[147]Hopcroft J, Motwani R, Ullman J. Introduction to Automata Theory, Languages and Computation. Reading, Mass:Addison-Wesley,1979.
[148]Zhang X, Zeng X, Pan L. On string languages generated by spiking neural P systems with exhaus-tive use of rules. Natural Computing,2008,7(4):535-549.
[149]Zeng X, Zhang X, Pan L. Homogeneous spiking neural P systems Fundamenta Informaticae, 2009,97:275-294.
[150]Korec I. Small universal register machines. Theoretical Computer Science,1996,168:267-301.
[151]Ishdorj T, Leporati A, Pan L, Wang J. Solving NP-Complete Problems by Spiking Neural P Systems with Budding Rules. Membrane Computing,2010,5957:335-353.
[152]Freund R, Oswald M. Spiking neural P systems with inhibitory axons. in:Sugisaka M, Tanaka H, editors, Proceedings of Proc. International Symposium on Artificial Life and Robotics, Beppu, Oita, Japan,2007.
[153]Wang S, Miao Z, Shi X. Solving 3-coloring problem by tissue P systems with cell separation, in: Xu J, Zhao D, Qiang X, editors, Proceedings of Proc.4th International Conference on Bio-inspired Computing:Theories and Application,2009,224-229.
[154]Jiang Y, Zhang X, Zhang Z. A uniform solution to Subset Sum by tissue P systems with cell separation. Journal of Computational and Theoretical Nanoscience,2010,7(8):1507-1513.
[155]Pan L, Paun Gh. Spiking neural P systems:An improved normal form. Theoretical Computer Science,2010,411:906-918.
[156]Baranda A, Castellanos J, Arroyo F, et al. Bio-language for computing with membranes, advances in artificial life. Lecture Notes on Computer Science,2001,2159:176-185.
[157]Suzuki Y, Fujiwara Y, Takabayashi J, et al. Artificial life applications of a class of P systems: abstract rewriting systems on multisets. Lecture Notes on Computer Science,2001,2235:299-346.
[158]Fontana F, Bianco L, Manca V. P systems and the modeling of biochemical oscillations. Lecture Notes on Computer Science,2006,3850:199-208.
[159]Bernardini F, Gheorghe M, Krasnogor N, et al. On P systems as a modeling tool for biological systems. Lecture Notes on Computer Science,2006,3850:114-133.
[160]Freund R, Ionescu M, Oswald M. Extended spiking neural P systems with decaying spikes and/or total spiking. International Journal of Foundations of Computer Science,2008,19:1223-1234.
[161]Paun Gh. Membrane Computing:An Introduction. Springer-Verlag:Springer,2002.