Mostrar el registro sencillo del ítem
Ponencia
On the Computational Power of Spiking Neural P Systems
dc.creator | Leporati, Alberto | |
dc.creator | Zandron, Claudio | |
dc.creator | Ferretti, Claudio | |
dc.creator | Mauri, Giancarlo | |
dc.date.accessioned | 2016-03-16T09:07:41Z | |
dc.date.available | 2016-03-16T09:07:41Z | |
dc.date.issued | 2007 | |
dc.identifier.isbn | 97861167760 | es |
dc.identifier.uri | http://hdl.handle.net/11441/38596 | |
dc.description.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. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | 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 | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | On the Computational Power of Spiking Neural P Systems | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/38596 |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
spiking.pdf | 254.1Kb | [PDF] | Ver/ | |