On Spiking Neural Membrane Systems with Neuron and Synapse Creation

Spiking neural membrane systems are models of computation inspired by the natural functioning of the brain using the concepts of neurons and synapses, and represent a way of building computational systems of a biological inspiration. A variant of such a model, allowing to create new neurons and synapses during the computation, has been considered in the literature to attack computationally hard problems, like problems in the class NP. In this work, we investigate the computational properties of this variant, by proposing three solutions to computationally hard problems, by models with different features, and comparing them with those present in the literature. In particular, we first propose a nondeterministic solution for the NP-complete problem 3-SAT, by a model using dynamic organization of synapses. Then, we propose a deterministic solution for the same problem, by a model using neuron division and dissolution rules. Finally, we show that dissolution rules are not strictly necessary (by accepting a certain amount of slowdown in computing time), and that also problems beyond the class NP can be solved by systems with neuron division alone.