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.

Gatti, M., Leporati, A., Zandron, C. (2022). On Spiking Neural Membrane Systems with Neuron and Synapse Creation. INTERNATIONAL JOURNAL OF NEURAL SYSTEMS, 32(8) [10.1142/S0129065722500368].

On Spiking Neural Membrane Systems with Neuron and Synapse Creation

Leporati A.;Zandron C.
2022

Abstract

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.
Articolo in rivista - Articolo scientifico
computational complexity; NP problems; spiking neural membrane systems;
English
2022
32
8
2250036
none
Gatti, M., Leporati, A., Zandron, C. (2022). On Spiking Neural Membrane Systems with Neuron and Synapse Creation. INTERNATIONAL JOURNAL OF NEURAL SYSTEMS, 32(8) [10.1142/S0129065722500368].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/395837
Citazioni
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
Social impact