Repositorio de producción científica de la Universidad de Sevilla

On the Computational Power of Spiking Neural P Systems


Advanced Search
Opened Access On the Computational Power of Spiking Neural P Systems
Show item statistics
Export to
Author: Leporati, Alberto
Zandron, Claudio
Ferretti, Claudio
Mauri, Giancarlo
Date: 2007
Published in: Proceedings of the Fifth Brainstorming Week on Membrane Computing, 227-245. Sevilla, E.T.S. de Ingeniería Informática, 29 de Enero-2 de Febrero, 2007
ISBN/ISSN: 97861167760
Document type: Presentation
Abstract: In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP-complete problem Subset Sum and the strongly NP-complete problem 3-SAT. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that the simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted type.
Size: 254.1Kb
Format: PDF


This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)