期刊
THEORETICAL COMPUTER SCIENCE
卷 411, 期 6, 页码 906-918出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2009.11.010
关键词
Membrane computing; Spiking neural P system; Turing computability; Semilinear set
资金
- National Natural Science Foundation of China [60674106, 30870826, 60703047, 60533010]
- Program for New Century Excellent Talents in University [NCET-05-0612]
- Ph.D. Programs Foundation of Ministry of Education of China [20060487014]
- Chenguang Program of Wuhan [200750731262]
- HUST-SRF [2007Z015A]
- Natural Science Foundation of Hubei Province [2008CDB113, 2008CDB180]
- Proyecto de Excelencia con Investigador de Reconocida Valia
- de la junta de Andalucia [P08 - TIC 04200]
Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computational (Such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems Without forgetting rules and delay remains to be found. (C) 2009 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据