Open AccessSpiking Neural P Systems with Neuron Division and Dissolution
Author(s) -
Yuzhen Zhao,
Xiyu Liu,
Wenping Wang
Publication year - 2016
Publication title -
plos one
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.99
H-Index - 332
ISSN - 1932-6203
DOI - 10.1371/journal.pone.0162882
Subject(s) - computer science , division (mathematics) , artificial neural network , computation , neuron , spiking neural network , time complexity , algorithm , theoretical computer science , mathematics , artificial intelligence , neuroscience , biology , arithmetic
Spiking neural P systems are a new candidate in spiking neural network models. By using neuron division and budding, such systems can generate/produce exponential working space in linear computational steps, thus provide a way to solve computational hard problems in feasible (linear or polynomial) time with a “time-space trade-off” strategy. In this work, a new mechanism called neuron dissolution is introduced, by which redundant neurons produced during the computation can be removed. As applications, uniform solutions to two NP-hard problems: SAT problem and Subset Sum problem are constructed in linear time, working in a deterministic way. The neuron dissolution strategy is used to eliminate invalid solutions, and all answers to these two problems are encoded as indices of output neurons. Our results improve the one obtained in Science China Information Sciences , 2011, 1596-1607 by Pan et al.