Journal
THEORETICAL COMPUTER SCIENCE
Volume 411, Issue 6, Pages 906-918Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2009.11.010
Keywords
Membrane computing; Spiking neural P system; Turing computability; Semilinear set
Categories
Funding
- 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]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available