脉冲神经膜系统的计算能力研究
|
摘要
硅基微电子器件线宽小于10纳米以后，来自器件工作原理、工艺技术与制造成本等方面的限制将形成难以克服的障碍。突破硅基器件的框框，发展非传统的新技术是当前计算机科学领域的研究前沿和热点。膜计算是非传统计算领域之一。膜系统，也称P系统，是一类分布式并行计算模型。该类计算模型主要是受细胞、组织、器官或其它生物结构处理化学物质的方式启发而建立起来的。由于其良好的计算性能以及在语言学、图形学、系统生物学、组合优化等领域的广泛应用价值，受到许多学者的关注。本文研究一类特殊的P系统，即脉冲神经膜系统，简称SNP系统。它是基于大脑中神经元之间通过突触相互协作、处理脉冲信息的生物现象而抽象出来的一种新计算模型。论文从语言(或数的)产生能力、小通用性以及计算有效性三个方面研究了脉冲神经膜系统的计算能力，主要工作如下：
首先研究了脉冲神经膜系统的语言(或数的)产生能力。计算设备的语言(或数的)产生能力是研究计算设备计算能力的基本问题之一。关于脉冲神经膜系统，本文研究了三类具体系统的语言(或数的)产生能力，即穷举使用规则的脉冲神经膜系统、非同步脉冲神经膜系统以及轴突膜系统。
对于穷举使用规则的脉冲神经膜系统，在限制性和非限制性两种语言的定义下，分别研究了它在使用延展规则时的语言产生能力。在两种情形下，都证明了延展脉冲神经膜系统在穷举使用规则模式下可以刻画有限语言和递归可枚举语言，同时还研究了与正则语言的关系。由于在非同步模式下，考虑系统的计算时间是没有意义的，因此在非同步脉冲神经膜系统中只能定义非限制性语言。在这种语言定义下，研究了非同步脉冲神经膜系统在使用延展规则时的语言产生能力，得到具有延展规则的非同步脉冲神经膜系统可以刻画有限语言和递归可枚举语言，同时还研究了它所产生的语言与正则语言以及非半线性语言的关系。另外，分别研究了轴突膜系统作为数的产生装置和语言产生装置时的产生能力：作为数的产生装置，得到了轴突膜系统产生的数集与有穷数集和半线性数集的关系；作为语言产生装置，得到了轴突膜系统产生的语言与有限语言和上下文无关语言的关系。
其次对脉冲神经膜系统的小通用性进行了研究。计算模型的小通用性是计算机科学中经典的研究问题之一。对于脉冲神经膜系统而言，研究小通用性问题除了计算机科学意义外，还有其生物学意义：给出某种小通用“脑”的度量。本文对脉冲神经膜系统的小通用性进行了如下研究：
针对A．P(?)un等人所构造的小通用脉冲神经膜系统，讨论了如何优化它们所使用的神经元个数的问题，提出了加法模块、减法模块以及加法与减法模块之间在一定情形下可以共用附属神经元的思想。通过详细分析任两个指令所对应的模块可以共用附属神经元的各种情形，把所模拟的小通用注册机的指令进行分类，使每组指令共用相同的附属神经元，从而得到了具有更少神经元个数的小通用脉冲神经膜系统。另外，在作为计算函数的装置和产生数的装置两种情形下，本文分别构造了穷举使用规则的小通用脉冲神经膜系统，并通过考虑附属神经元共用的情形，优化了所得到的小通用性系统的神经元个数。
最后研究了脉冲神经膜系统的计算有效性。由于脉冲神经膜系统的拓扑结构是固定的，在计算过程中无法由脉冲神经膜系统本身来生成计算空间，从而实现空间换时间。因此，本文研究了脉冲神经膜系统在使用指数规模的预计算资源(即系统包含指数个神经元)时的计算有效性。利用这种类型的系统，给出了一族求解QSAT问题的脉冲神经膜系统(QSAT问题是PSPACE完全问题)。在该族脉冲神经膜系统中，每个脉冲神经膜系统可以在多项式时间内(与问题规模相关)求解具有某一相同规模的QSAT问题的所有算例。
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.
首先研究了脉冲神经膜系统的语言(或数的)产生能力。计算设备的语言(或数的)产生能力是研究计算设备计算能力的基本问题之一。关于脉冲神经膜系统，本文研究了三类具体系统的语言(或数的)产生能力，即穷举使用规则的脉冲神经膜系统、非同步脉冲神经膜系统以及轴突膜系统。
对于穷举使用规则的脉冲神经膜系统，在限制性和非限制性两种语言的定义下，分别研究了它在使用延展规则时的语言产生能力。在两种情形下，都证明了延展脉冲神经膜系统在穷举使用规则模式下可以刻画有限语言和递归可枚举语言，同时还研究了与正则语言的关系。由于在非同步模式下，考虑系统的计算时间是没有意义的，因此在非同步脉冲神经膜系统中只能定义非限制性语言。在这种语言定义下，研究了非同步脉冲神经膜系统在使用延展规则时的语言产生能力，得到具有延展规则的非同步脉冲神经膜系统可以刻画有限语言和递归可枚举语言，同时还研究了它所产生的语言与正则语言以及非半线性语言的关系。另外，分别研究了轴突膜系统作为数的产生装置和语言产生装置时的产生能力：作为数的产生装置，得到了轴突膜系统产生的数集与有穷数集和半线性数集的关系；作为语言产生装置，得到了轴突膜系统产生的语言与有限语言和上下文无关语言的关系。
其次对脉冲神经膜系统的小通用性进行了研究。计算模型的小通用性是计算机科学中经典的研究问题之一。对于脉冲神经膜系统而言，研究小通用性问题除了计算机科学意义外，还有其生物学意义：给出某种小通用“脑”的度量。本文对脉冲神经膜系统的小通用性进行了如下研究：
针对A．P(?)un等人所构造的小通用脉冲神经膜系统，讨论了如何优化它们所使用的神经元个数的问题，提出了加法模块、减法模块以及加法与减法模块之间在一定情形下可以共用附属神经元的思想。通过详细分析任两个指令所对应的模块可以共用附属神经元的各种情形，把所模拟的小通用注册机的指令进行分类，使每组指令共用相同的附属神经元，从而得到了具有更少神经元个数的小通用脉冲神经膜系统。另外，在作为计算函数的装置和产生数的装置两种情形下，本文分别构造了穷举使用规则的小通用脉冲神经膜系统，并通过考虑附属神经元共用的情形，优化了所得到的小通用性系统的神经元个数。
最后研究了脉冲神经膜系统的计算有效性。由于脉冲神经膜系统的拓扑结构是固定的，在计算过程中无法由脉冲神经膜系统本身来生成计算空间，从而实现空间换时间。因此，本文研究了脉冲神经膜系统在使用指数规模的预计算资源(即系统包含指数个神经元)时的计算有效性。利用这种类型的系统，给出了一族求解QSAT问题的脉冲神经膜系统(QSAT问题是PSPACE完全问题)。在该族脉冲神经膜系统中，每个脉冲神经膜系统可以在多项式时间内(与问题规模相关)求解具有某一相同规模的QSAT问题的所有算例。
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.
引文
[1] Linz P. An Introduction to Formal Languages and Automata (英文版). 北京: 机械工业出版社, 2004.
[2] Salomaa A. Formal Languages. New York: Academic Press, 1973.
[3] 孙家骗(等译)．形式语言与自动机导论．北京：机械工业出版社，2005．
[4] 蒋宗礼，姜守旭．形式语言与自动机理论．北京：清华大学出版社，2003．
[5] Minsky M. Computation-Finite and Infinite Machines. New Jersey: Prentice-Hall, Englewood Clifs, 1967.
[6] Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages and Computation. Reading, Mass.: Addison-Wesley, 1979.
[7] Kovahi Z. Switching and Finite Automata Theory. New York: McGraw-Hill, 1978.
[8] 李国杰．非传统的高性能计算技术．世界科技研究与发展，1998，20(3)：14-16．
[9] P(?)un Gh. Computing with membranes. Journal of Computer and System Sciences, 2000, 61 (1): 108-143 (first circulated at TUCS Research Report No 208, November 1998).
[10] P(?)un Gh, Rozenberg G. A guide to membrane computing. Theoretical Computer Science, 2002, 287: 73-100.
[11] Martin-Vide C, P(?)un A, P(?)un Gh. Membrane computing: new results, new problems. Bulletin of the EATCS, 2002, 78: 204-212.
[12] P(?)un Gh, P(?)rez-Jim(?)nez M J. Membrane computing: brief introduction, recent results and applications.Biosystems, 2006, 85(1): 11-22.
[13] P(?)un Gh. Membrane computing: power, efficiency, applications. Lecture Notes in Computer Science, 2005, 3526: 396-407.
[14] 许绍芬．神经生物学．上海：复旦大学出版社，2004．
[15] 史忠植．计算神经科学．http://www.intsci.ac.cn/research/neuroscience.html．
[16] Madhu M. Studies of P systems as a model of cellular computing: [PhD Dissertation]. Indian Institute of Technology Madras, 2003.
[17] Ishdorj T-O. Membrane computing, neural inspirations, gene assembly in ciliates: [PhD Dissertation]. University of Seville, 2006.
[18] Alhazov A. Communication in membrane systems with symbol objects: [PhD Dissertation]. University Rovira i Virgili, 2007.
[19] Bianco L. Membrane models of biological systems: [PhD Dissertation]. Universit(?) degli Studi di Verona, 2007.
[20] P(?)un Gh. Membrane Computing. An Introduction. Berlin: Springer, 2002.
[21] Ciobanu G, P(?)rez-Jim(?)nez M J, P(?)un Gh. Applications of Membrane Computing. Berlin: Springer, 2006.
[22] Mart(?)-vide C, P(?)un Gh, Rozenberg G. Membrane systems with carriers. Theoretical Computer Science, 2002, 270: 779-796.
[23] Mart(?)-vide C, P(?)un Gh, Pazos J, et al. Tissue P systems. Theoretical Computer Science, 2003, 296(2): 295-326.
[24] Cavaliere M, Genova D. P systems with symport/antiport of rules. Journal of Universal Computer Science, 2004, 10(5): 540-558.
[25] Bernardini F, Gheorghe M, Holcombe M. Eilenberg P systems with symbol-objects. Lecture Notes in Computer Science, 2004, 2950: 288-301.
[26] Bernardini F, Gheorghe M. Population P systems. Journal of Universal Computer Science, 2004, 10(5): 509-539.
[27] P(?)un A, Popa B. P systems with proteins on membranes and membrane division. Lecture Notes in Computer Science, 2006, 4036: 292-303.
[28] Dassow J, P(?)un Gh. On the power of membrane computing. Journal of Universal Computer Science, 1999, 5(2): 33-49.
[29] Freund R, P(?)un A. Membrane systems with symport/antiport rules: universality results. Lecture Notes in Computer Science, 2003, 2957: 270-287.
[30] Freund R, Kari L, Oswald M, et al. Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 2005, 330(2): 251-266.
[31] Sosik P, Freund R. P systems without priorities are computationally universal. Theoretical Computer Science, 2003, 2597: 400-409.
[32] Pan L Q, 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.
[33] Guti(?)rrez-naranjo M A, P(?)rez-jim(?)nez M J, Romero-campero F J. Uniform solution of QSAT using polarizationless active membranes. Lecture Notes in Computer Science, 2007, 4664: 122-133.
[34] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Romero-Campero F J. A linear solution of subset sum problem by using membrane creation. Lecture Notes in Computer Science, 2005, 3561: 258-267.
[35] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Romero-Campero F J. A uniform solutin to SAT using membrane creation. Theoretical Computer Science, 2007, 371: 54-61.
[36] Pan L Q, Mart(?)-vide C. Further remark on P systems with active membranes and two polarizations. Journal of Parallel and Distributed Computing, 2006, 66: 867-872.
[37] Pan L Q, Alhazov A, Isdorj T-O. Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Computing, 2005, 9(9): 686-690.
[38] Nishida T Y. Membrane algorithms. Lecture Notes in Computer Science, 2006, 3850: 55-66.
[39] Nishida T Y. An approximate algorithm for NP-complete optimization problem exploiting P systems. In: Proceedings of Brainstorming Workshop on Uncertainty in Membrane Computing, 2004,185-192.
[40] Nishida T Y. An application of P systems: a new algorithm for NP-complete optimization problem. In: Proceedings of Eighth World Multi-Conference on Systems, Cybernetics and Informatics,2004,109-112.
[41] Huang L, Wang N. An optimization algorithm inspired by membrane computing. Lecture Notes in Computer Science, 2006, 4222: 49-52.
[42] Zhang Y, Huang L. A variant of P systems for optimization. Neurocomputing, 2009, 72: 1355-1360.
[43] Zhang G X, Gheorghe M, Wu C Z. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae, 2008, 87: 1-24.
[44] Bianco L, Pescini D, Siepmann P, et al. Towards a P systems pseudomonas quorum sensing model. Lecture Notes in Computer Science, 2006,4361: 197-214.
[45] Mauri G. Membrane systems and their application to systems biology. Biosystems, 2007, 4497: 551-553.
[46] Bianco L, Pescini D, Siepmann P, et al. P systems applications to systems biology. Biosystems, 2008, 91(3): 435-437.
[47] Nagy B, Szegedi L. Membrane computing and graphical operating systems. Journal of Universal Computer Science, 2006, 12(9): 1312-1331.
[48] Bel-Enguix G. Unstable P systems: applications to linguistics. Lecture Notes in Computer Science, 2005,3365: 190-209.
[49] Bel-Enguix G, Gramatovici R. Parsing with active P automata. Lecture Notes in Computer Science, 2004,2933:419-463.
[50] Ceterchi R, Martin-Vide C. P systems with communication for static sorting. In: Pre-Proceedings of Brainstorming Week on Membrane Computing, 2003, 101-117.
[51] Alhazov A, Sburlan D. Static sorting algorithms for P systems. In: Pre-Proceedings of the Workshop on Membrane Computing, 2003, 17-40.
[52] Daniela B, Paolo C, Dario P. Seasonal variance in P system models for metapopulations. Progress in Natural Science, 2007, 17(4): 392-400.
[53] Daniela B, Paolo C, Dario P. Modelling metapopulations with stochastic membrane systems. Biosystems, 2008, 91(3): 499-514.
[54] P(?)un Gh. Tracing some open problems in membrane computing. Romanian Journal of Information Science and Technology, 2007, 10(4): 303-314.
[55] Bernardini F, Gheorghe M, Krasnogor N, et al. Membrane computing - current results and future problems. Lecture Notes in Computer Science, 2005, 3526: 49-53.
[56] P(?)un Gh. Further twenty six open problems in membrane computing. In: Proceedings of the Third Brainstorming Week on Membrane Computing, 2005, 249-262.
[57] Ionescu M, P(?)un Gh, Yokomori T. Spiking neural P systems. Fundamenta Informaticae, 2006, 71(2-3): 279-308.
[58] P(?)un Gh. Spiking neural P systems, power and efficiency. Lecuture Notes in Computer Science, 2007,4527: 153-169.
[59] P(?)un Gh, P(?)rez-Jim(?)nez M J. Spiking neural P systems, recent results, research topics. Submitted.
[60] P(?)un Gh, P(?)rez-Jim(?)nez M J, Slonmma A. Spiking neural P systems. An early survey. Interna- tional Journal of Foundations of Computer Science, 2007,18(6): 1371-1382.
[61] P(?)un 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.
[62] P(?)un Gh. Spiking neural P systems. A tutorial. Bulletin of the EATCS, 2007, 91: 145-159.
[63] P(?)un Gh, Perez-jimenez M J, Rozenberg G. Spike trains in spiking neural P systems. International Journal of Foundations of Computer Science, 2006, 17(4): 975-1002.
[64] P(?)un Gh, Perez-jimenez M J, Rozenberg G. Infinte spike trains in spiking neural P systems. Submitted.
[65] Chen H M, Ionescu M, Ishdorj T-O, et al. Spiking neural P systems with extended rules. In: Proceedings of the Fourth Brainstorming Week on Membrane Computing, 2006,241-266.
[66] Ionescu M, P(?)un A, Paun Gh, 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.
[67] Chen H M, Ionescu M, P(?)un A, et al. Computing with spiking neural P systems: traces and small universal systems. Lecture Notes in Computer Science, 2006,4287: 1-16.
[68] P(?)un Gh. Spiking neural P systems used as acceptors and transdecers. Lecture Notes in Computer Science, 2007,4783: 1-4.
[69] Chen H M, Ionescu M, Ishdorj T-O, et al. Spiking neural P systems with extended rules: universality and languages. Natural Computing, 2008,7(2): 147-166.
[70] Ionescu M, P(?)un Gh, Yokomori T. Spiking neural P systems with exhaustive use of rules. International Journal of Unconventional Computing, 2007, 3(2): 135-154.
[71] Cavaliere M, Egecioglu O, Ibarra O H, et al. Asynchronous spiking neural P systems. Technical Report 9/2007, Microsoft Research -University of Trento, Centre for Computational and Systems Biology.
[72] Ibarra O H, Woodworm S, Yu F, et al. On spiking neural P systems and partially blind counter machines. Lecture Notes in Computer Science, 2006,4135: 113-129.
[73] Freund R, Ionescu M, Oswald M. Extended spiking neural P systems with decaying spikes and/or total spiking. In: Proceedings of the International Workshop, Automata for Cellular and Molecular Computing, 2007, 64-75.
[74] Yuan Z M, Zhang Z G. Asynchronous spiking neural P systems with promoters. Lecture Notes in Computer Science, 2007,4847: 693-702.
[75] Ibarra O H, Woodworth S. Characterizations of some restricted spiking neural P systems. Lecture Notes in Computer Science, 2006,4361: 424-442.
[76] Ibarra O H, P(?)un A, P(?)un Gh, et aL. Normal forms for spiking neural P systems. Theoretical Computer Science, 2007, 372(2-3): 196-217.
[77] Garc(?)a-Arnau M, Per(?)z D, Rodr(?)guez-Pat(?)n A, et al. Spiking neural P systems: stronger normal forms. In: Proceedings of the Fifth Brainstorming Week on Membrane Computing, 2007, 157-178.
[78] Chen H, Freund R, Ionescu M, et al. On string languages generated by spiking neural P systems. Fundamenta Informaticae, 2007,75: 141-162.
[79] Ibarra OH, Woodworth S. Characterizing regular languages by spiking neural P systems. Interna- tional Journal of Foundations of Computer Science, 2007, 18(6): 1247-1256.
[80] Freund R, Oswald M. Regular w-language denned by finite extended spiking neural P systems. Fundamenta Informaticae, 2008, 83(1-2): 65-73.
[81] Chen H M, Ishdorj T-O, P(?)un Gh. Handling languages with spiking neural P systems with extended rules. Romanian Journal of Information Science and Technology, 2006, 9(3): 151-162.
[82] Cavaliere O, Egecioglu O, Ibarra O H, et al. Asynchronous spiking neural P systems: decidability and undecidability. Lecture Notes in Computer Science, 2008,4848: 264-255.
[83] Ibarra O H, Woodworth S. Characterizations of some classes of spiking neural P systems. Natural Computing, 2008, 7(4): 499-517.
[84] P(?)un A, P(?)un Gh. Small universal spiking neural P systems. Biosystems, 2007,90(1): 48-60.
[85] Leporati A, Zandron C, Ferretti C, et al. On the computational power of spiking neural P systems.International Journal of Unconventional Computing (to appear).
[86] Chen H M, Ionescu M, Ishdorj T-O. On the efficiency of spiking neural P systems. In: Proceedings of the Eighth International Conference on Electronics, Information, and Communication, 2006,49-52.
[87] Ishdorj T-O, 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.
[88] Guti(?)rrez-Naranjo M A, Leporati A. Solving subset sum by spiking neural P systems with pre-computed resources. Fundamenta Informaticae, 2008, 87(1): 61-77.
[89] Leporati A, Zandron C, Ferretti C, et al. Solving numerical NP-complete problems with spiking neural P systems. Lecture Notes in Computer Science, 2007,4860: 336-352.
[90] Leporati A, Mauri G, Zandron C, et al. Uniform solutions to SAT and subset sum by spiking neural P systems. Natural Computing, DOI: 10.1007/s1 1047-008-9091-y.
[91] Ionescu M, Paun Gh, Yokomori T. Some applications of spiking neural P systems. In: Proceedings of the Eighth Workshop on Membrane Computing, 2007, 383-394.
[92] Ceterchi R, Tomescu A I. Implementing sorting networks with spiking neural P systems. Fundamenta Informaticae, 2008, 87(1): 35-48.
[93] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J. A spiking neural P system based model for hebbian learning. In: Proceedings of the Ninth Workshop on Membrane Computing, 2008, 189-207.
[94] Meta V P, Krithivasan K. Spiking neural P systems and petri nets. Submitted.
[95] Binder A, Freund R, Oswald M, et al. Extended spiking neural P systems with excitatory and inhibitory astrocytes. In: Proceedings of the Eighth Conference on Eighth WSEAS International Conference on Evolutionary Computing, 2007, 320-325.
[96] P(?)un Gh. Spiking neural P systems with astrocyte-like control. Journal of Universal Computer Science,2007,13(11): 1701-1721.
[97] Chen H M, Ishdorj T-O, Paun Gh. Computing along the axon. Progress in Natual Science, 2007, 17(4): 417-423.
[98] P(?)un Gh. Twenty six research topics about spiking neural P systems. Lecture Notes in Computer Science, 2007,4527: 153-169.
[99] Korec I. Small universal register machines. Theoretical Computer Science, 1996, 168: 267-301.
[100] Garey M R, Johnson D S. Computers and Intractability. A Guide to the Theory of NP-completeness. San Francisco: W.H. Freeman and Company, 1979.
[101] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Ram(?)rez-Mart(?)nez D. A software tool for verification of spiking neural P systems. Natural Computing, 2008, 7(4): 485-497.
[102] Baranda A, Arroyo F, Castellanos J, et al. Bio-language for computing with membranes, advances in artificial life. Lecture Notes in Computer Science, 2001,2159: 176-185.
[103] Suzuki Y, Fujiwara Y, Tanaka H, et al. Artifical life applications of a class of P systems: abstract rewriting systems on multisets. Lecture Notes in Computer Science, 2001, 2235: 299-346.
[104] P(?)rez-Jim(?)nez M J, Romero-Campero F J. A study of the robustness of the EGFR signalling cascade using continuous membrane systems. Lecture Notes in Computer Science, 2005, 3561: 268-278.
[105] Fontana F, Bianco L, Manca V. P systems and the modeling of biochemical oscillations. Lecture Notes in Computer Science, 2006, 3850: 199-208.
[106] Bernardini F, Gheorghe M, Krasnogor N, et al. On P systems as a modelling tool for biological systems. Lecture Notes in Computer Science, 2006, 3850: 114-133.
[107] Ji S. The bhopalator: an information/energy dual model of the living cell. Fundamenta Informaticae, 2002,49(1): 147-165.
[2] Salomaa A. Formal Languages. New York: Academic Press, 1973.
[3] 孙家骗(等译)．形式语言与自动机导论．北京：机械工业出版社，2005．
[4] 蒋宗礼，姜守旭．形式语言与自动机理论．北京：清华大学出版社，2003．
[5] Minsky M. Computation-Finite and Infinite Machines. New Jersey: Prentice-Hall, Englewood Clifs, 1967.
[6] Hopcroft J E, Ullman J D. Introduction to Automata Theory, Languages and Computation. Reading, Mass.: Addison-Wesley, 1979.
[7] Kovahi Z. Switching and Finite Automata Theory. New York: McGraw-Hill, 1978.
[8] 李国杰．非传统的高性能计算技术．世界科技研究与发展，1998，20(3)：14-16．
[9] P(?)un Gh. Computing with membranes. Journal of Computer and System Sciences, 2000, 61 (1): 108-143 (first circulated at TUCS Research Report No 208, November 1998).
[10] P(?)un Gh, Rozenberg G. A guide to membrane computing. Theoretical Computer Science, 2002, 287: 73-100.
[11] Martin-Vide C, P(?)un A, P(?)un Gh. Membrane computing: new results, new problems. Bulletin of the EATCS, 2002, 78: 204-212.
[12] P(?)un Gh, P(?)rez-Jim(?)nez M J. Membrane computing: brief introduction, recent results and applications.Biosystems, 2006, 85(1): 11-22.
[13] P(?)un Gh. Membrane computing: power, efficiency, applications. Lecture Notes in Computer Science, 2005, 3526: 396-407.
[14] 许绍芬．神经生物学．上海：复旦大学出版社，2004．
[15] 史忠植．计算神经科学．http://www.intsci.ac.cn/research/neuroscience.html．
[16] Madhu M. Studies of P systems as a model of cellular computing: [PhD Dissertation]. Indian Institute of Technology Madras, 2003.
[17] Ishdorj T-O. Membrane computing, neural inspirations, gene assembly in ciliates: [PhD Dissertation]. University of Seville, 2006.
[18] Alhazov A. Communication in membrane systems with symbol objects: [PhD Dissertation]. University Rovira i Virgili, 2007.
[19] Bianco L. Membrane models of biological systems: [PhD Dissertation]. Universit(?) degli Studi di Verona, 2007.
[20] P(?)un Gh. Membrane Computing. An Introduction. Berlin: Springer, 2002.
[21] Ciobanu G, P(?)rez-Jim(?)nez M J, P(?)un Gh. Applications of Membrane Computing. Berlin: Springer, 2006.
[22] Mart(?)-vide C, P(?)un Gh, Rozenberg G. Membrane systems with carriers. Theoretical Computer Science, 2002, 270: 779-796.
[23] Mart(?)-vide C, P(?)un Gh, Pazos J, et al. Tissue P systems. Theoretical Computer Science, 2003, 296(2): 295-326.
[24] Cavaliere M, Genova D. P systems with symport/antiport of rules. Journal of Universal Computer Science, 2004, 10(5): 540-558.
[25] Bernardini F, Gheorghe M, Holcombe M. Eilenberg P systems with symbol-objects. Lecture Notes in Computer Science, 2004, 2950: 288-301.
[26] Bernardini F, Gheorghe M. Population P systems. Journal of Universal Computer Science, 2004, 10(5): 509-539.
[27] P(?)un A, Popa B. P systems with proteins on membranes and membrane division. Lecture Notes in Computer Science, 2006, 4036: 292-303.
[28] Dassow J, P(?)un Gh. On the power of membrane computing. Journal of Universal Computer Science, 1999, 5(2): 33-49.
[29] Freund R, P(?)un A. Membrane systems with symport/antiport rules: universality results. Lecture Notes in Computer Science, 2003, 2957: 270-287.
[30] Freund R, Kari L, Oswald M, et al. Computationally universal P systems without priorities: two catalysts are sufficient. Theoretical Computer Science, 2005, 330(2): 251-266.
[31] Sosik P, Freund R. P systems without priorities are computationally universal. Theoretical Computer Science, 2003, 2597: 400-409.
[32] Pan L Q, 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.
[33] Guti(?)rrez-naranjo M A, P(?)rez-jim(?)nez M J, Romero-campero F J. Uniform solution of QSAT using polarizationless active membranes. Lecture Notes in Computer Science, 2007, 4664: 122-133.
[34] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Romero-Campero F J. A linear solution of subset sum problem by using membrane creation. Lecture Notes in Computer Science, 2005, 3561: 258-267.
[35] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Romero-Campero F J. A uniform solutin to SAT using membrane creation. Theoretical Computer Science, 2007, 371: 54-61.
[36] Pan L Q, Mart(?)-vide C. Further remark on P systems with active membranes and two polarizations. Journal of Parallel and Distributed Computing, 2006, 66: 867-872.
[37] Pan L Q, Alhazov A, Isdorj T-O. Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Computing, 2005, 9(9): 686-690.
[38] Nishida T Y. Membrane algorithms. Lecture Notes in Computer Science, 2006, 3850: 55-66.
[39] Nishida T Y. An approximate algorithm for NP-complete optimization problem exploiting P systems. In: Proceedings of Brainstorming Workshop on Uncertainty in Membrane Computing, 2004,185-192.
[40] Nishida T Y. An application of P systems: a new algorithm for NP-complete optimization problem. In: Proceedings of Eighth World Multi-Conference on Systems, Cybernetics and Informatics,2004,109-112.
[41] Huang L, Wang N. An optimization algorithm inspired by membrane computing. Lecture Notes in Computer Science, 2006, 4222: 49-52.
[42] Zhang Y, Huang L. A variant of P systems for optimization. Neurocomputing, 2009, 72: 1355-1360.
[43] Zhang G X, Gheorghe M, Wu C Z. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae, 2008, 87: 1-24.
[44] Bianco L, Pescini D, Siepmann P, et al. Towards a P systems pseudomonas quorum sensing model. Lecture Notes in Computer Science, 2006,4361: 197-214.
[45] Mauri G. Membrane systems and their application to systems biology. Biosystems, 2007, 4497: 551-553.
[46] Bianco L, Pescini D, Siepmann P, et al. P systems applications to systems biology. Biosystems, 2008, 91(3): 435-437.
[47] Nagy B, Szegedi L. Membrane computing and graphical operating systems. Journal of Universal Computer Science, 2006, 12(9): 1312-1331.
[48] Bel-Enguix G. Unstable P systems: applications to linguistics. Lecture Notes in Computer Science, 2005,3365: 190-209.
[49] Bel-Enguix G, Gramatovici R. Parsing with active P automata. Lecture Notes in Computer Science, 2004,2933:419-463.
[50] Ceterchi R, Martin-Vide C. P systems with communication for static sorting. In: Pre-Proceedings of Brainstorming Week on Membrane Computing, 2003, 101-117.
[51] Alhazov A, Sburlan D. Static sorting algorithms for P systems. In: Pre-Proceedings of the Workshop on Membrane Computing, 2003, 17-40.
[52] Daniela B, Paolo C, Dario P. Seasonal variance in P system models for metapopulations. Progress in Natural Science, 2007, 17(4): 392-400.
[53] Daniela B, Paolo C, Dario P. Modelling metapopulations with stochastic membrane systems. Biosystems, 2008, 91(3): 499-514.
[54] P(?)un Gh. Tracing some open problems in membrane computing. Romanian Journal of Information Science and Technology, 2007, 10(4): 303-314.
[55] Bernardini F, Gheorghe M, Krasnogor N, et al. Membrane computing - current results and future problems. Lecture Notes in Computer Science, 2005, 3526: 49-53.
[56] P(?)un Gh. Further twenty six open problems in membrane computing. In: Proceedings of the Third Brainstorming Week on Membrane Computing, 2005, 249-262.
[57] Ionescu M, P(?)un Gh, Yokomori T. Spiking neural P systems. Fundamenta Informaticae, 2006, 71(2-3): 279-308.
[58] P(?)un Gh. Spiking neural P systems, power and efficiency. Lecuture Notes in Computer Science, 2007,4527: 153-169.
[59] P(?)un Gh, P(?)rez-Jim(?)nez M J. Spiking neural P systems, recent results, research topics. Submitted.
[60] P(?)un Gh, P(?)rez-Jim(?)nez M J, Slonmma A. Spiking neural P systems. An early survey. Interna- tional Journal of Foundations of Computer Science, 2007,18(6): 1371-1382.
[61] P(?)un 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.
[62] P(?)un Gh. Spiking neural P systems. A tutorial. Bulletin of the EATCS, 2007, 91: 145-159.
[63] P(?)un Gh, Perez-jimenez M J, Rozenberg G. Spike trains in spiking neural P systems. International Journal of Foundations of Computer Science, 2006, 17(4): 975-1002.
[64] P(?)un Gh, Perez-jimenez M J, Rozenberg G. Infinte spike trains in spiking neural P systems. Submitted.
[65] Chen H M, Ionescu M, Ishdorj T-O, et al. Spiking neural P systems with extended rules. In: Proceedings of the Fourth Brainstorming Week on Membrane Computing, 2006,241-266.
[66] Ionescu M, P(?)un A, Paun Gh, 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.
[67] Chen H M, Ionescu M, P(?)un A, et al. Computing with spiking neural P systems: traces and small universal systems. Lecture Notes in Computer Science, 2006,4287: 1-16.
[68] P(?)un Gh. Spiking neural P systems used as acceptors and transdecers. Lecture Notes in Computer Science, 2007,4783: 1-4.
[69] Chen H M, Ionescu M, Ishdorj T-O, et al. Spiking neural P systems with extended rules: universality and languages. Natural Computing, 2008,7(2): 147-166.
[70] Ionescu M, P(?)un Gh, Yokomori T. Spiking neural P systems with exhaustive use of rules. International Journal of Unconventional Computing, 2007, 3(2): 135-154.
[71] Cavaliere M, Egecioglu O, Ibarra O H, et al. Asynchronous spiking neural P systems. Technical Report 9/2007, Microsoft Research -University of Trento, Centre for Computational and Systems Biology.
[72] Ibarra O H, Woodworm S, Yu F, et al. On spiking neural P systems and partially blind counter machines. Lecture Notes in Computer Science, 2006,4135: 113-129.
[73] Freund R, Ionescu M, Oswald M. Extended spiking neural P systems with decaying spikes and/or total spiking. In: Proceedings of the International Workshop, Automata for Cellular and Molecular Computing, 2007, 64-75.
[74] Yuan Z M, Zhang Z G. Asynchronous spiking neural P systems with promoters. Lecture Notes in Computer Science, 2007,4847: 693-702.
[75] Ibarra O H, Woodworth S. Characterizations of some restricted spiking neural P systems. Lecture Notes in Computer Science, 2006,4361: 424-442.
[76] Ibarra O H, P(?)un A, P(?)un Gh, et aL. Normal forms for spiking neural P systems. Theoretical Computer Science, 2007, 372(2-3): 196-217.
[77] Garc(?)a-Arnau M, Per(?)z D, Rodr(?)guez-Pat(?)n A, et al. Spiking neural P systems: stronger normal forms. In: Proceedings of the Fifth Brainstorming Week on Membrane Computing, 2007, 157-178.
[78] Chen H, Freund R, Ionescu M, et al. On string languages generated by spiking neural P systems. Fundamenta Informaticae, 2007,75: 141-162.
[79] Ibarra OH, Woodworth S. Characterizing regular languages by spiking neural P systems. Interna- tional Journal of Foundations of Computer Science, 2007, 18(6): 1247-1256.
[80] Freund R, Oswald M. Regular w-language denned by finite extended spiking neural P systems. Fundamenta Informaticae, 2008, 83(1-2): 65-73.
[81] Chen H M, Ishdorj T-O, P(?)un Gh. Handling languages with spiking neural P systems with extended rules. Romanian Journal of Information Science and Technology, 2006, 9(3): 151-162.
[82] Cavaliere O, Egecioglu O, Ibarra O H, et al. Asynchronous spiking neural P systems: decidability and undecidability. Lecture Notes in Computer Science, 2008,4848: 264-255.
[83] Ibarra O H, Woodworth S. Characterizations of some classes of spiking neural P systems. Natural Computing, 2008, 7(4): 499-517.
[84] P(?)un A, P(?)un Gh. Small universal spiking neural P systems. Biosystems, 2007,90(1): 48-60.
[85] Leporati A, Zandron C, Ferretti C, et al. On the computational power of spiking neural P systems.International Journal of Unconventional Computing (to appear).
[86] Chen H M, Ionescu M, Ishdorj T-O. On the efficiency of spiking neural P systems. In: Proceedings of the Eighth International Conference on Electronics, Information, and Communication, 2006,49-52.
[87] Ishdorj T-O, 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.
[88] Guti(?)rrez-Naranjo M A, Leporati A. Solving subset sum by spiking neural P systems with pre-computed resources. Fundamenta Informaticae, 2008, 87(1): 61-77.
[89] Leporati A, Zandron C, Ferretti C, et al. Solving numerical NP-complete problems with spiking neural P systems. Lecture Notes in Computer Science, 2007,4860: 336-352.
[90] Leporati A, Mauri G, Zandron C, et al. Uniform solutions to SAT and subset sum by spiking neural P systems. Natural Computing, DOI: 10.1007/s1 1047-008-9091-y.
[91] Ionescu M, Paun Gh, Yokomori T. Some applications of spiking neural P systems. In: Proceedings of the Eighth Workshop on Membrane Computing, 2007, 383-394.
[92] Ceterchi R, Tomescu A I. Implementing sorting networks with spiking neural P systems. Fundamenta Informaticae, 2008, 87(1): 35-48.
[93] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J. A spiking neural P system based model for hebbian learning. In: Proceedings of the Ninth Workshop on Membrane Computing, 2008, 189-207.
[94] Meta V P, Krithivasan K. Spiking neural P systems and petri nets. Submitted.
[95] Binder A, Freund R, Oswald M, et al. Extended spiking neural P systems with excitatory and inhibitory astrocytes. In: Proceedings of the Eighth Conference on Eighth WSEAS International Conference on Evolutionary Computing, 2007, 320-325.
[96] P(?)un Gh. Spiking neural P systems with astrocyte-like control. Journal of Universal Computer Science,2007,13(11): 1701-1721.
[97] Chen H M, Ishdorj T-O, Paun Gh. Computing along the axon. Progress in Natual Science, 2007, 17(4): 417-423.
[98] P(?)un Gh. Twenty six research topics about spiking neural P systems. Lecture Notes in Computer Science, 2007,4527: 153-169.
[99] Korec I. Small universal register machines. Theoretical Computer Science, 1996, 168: 267-301.
[100] Garey M R, Johnson D S. Computers and Intractability. A Guide to the Theory of NP-completeness. San Francisco: W.H. Freeman and Company, 1979.
[101] Guti(?)rrez-Naranjo M A, P(?)rez-Jim(?)nez M J, Ram(?)rez-Mart(?)nez D. A software tool for verification of spiking neural P systems. Natural Computing, 2008, 7(4): 485-497.
[102] Baranda A, Arroyo F, Castellanos J, et al. Bio-language for computing with membranes, advances in artificial life. Lecture Notes in Computer Science, 2001,2159: 176-185.
[103] Suzuki Y, Fujiwara Y, Tanaka H, et al. Artifical life applications of a class of P systems: abstract rewriting systems on multisets. Lecture Notes in Computer Science, 2001, 2235: 299-346.
[104] P(?)rez-Jim(?)nez M J, Romero-Campero F J. A study of the robustness of the EGFR signalling cascade using continuous membrane systems. Lecture Notes in Computer Science, 2005, 3561: 268-278.
[105] Fontana F, Bianco L, Manca V. P systems and the modeling of biochemical oscillations. Lecture Notes in Computer Science, 2006, 3850: 199-208.
[106] Bernardini F, Gheorghe M, Krasnogor N, et al. On P systems as a modelling tool for biological systems. Lecture Notes in Computer Science, 2006, 3850: 114-133.
[107] Ji S. The bhopalator: an information/energy dual model of the living cell. Fundamenta Informaticae, 2002,49(1): 147-165.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |