dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.creator | Romero Campero, Francisco José | es |
dc.date.accessioned | 2017-02-06T10:39:28Z | |
dc.date.available | 2017-02-06T10:39:28Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Gutiérrez Naranjo, M.Á., Pérez Jiménez, M.d.J., Riscos Núñez, A. y Romero Campero, F.J. (2006). Computational efficiency of dissolution rules in membrane systems. International Journal of Computer Mathematics, 83 (7), 593-611. | |
dc.identifier.issn | 0020-7160 | es |
dc.identifier.uri | http://hdl.handle.net/11441/53705 | |
dc.description.abstract | Trading (in polynomial time) space for time in the framework of membrane systems is not sufficient to
efficiently solve computationally hard problems. On the one hand, an exponential number of objects
generated in polynomial time is not sufficient to solve NP-complete problems in polynomial time.
On the other hand, when an exponential number of membranes is created and used as workspace, the
situation is very different. Two operations in P systems (membrane division and membrane creation)
capable of constructing an exponential number of membranes in linear time are studied in this paper.
NP-complete problems can be solved in polynomial time using P systems with active membranes
and with polarizations, but when electrical charges are not used, then dissolution rules turn out to
be very important. We show that in the framework of P systems with active membranes but without
polarizations and in the framework of P systems with membrane creation, dissolution rules play a
crucial role from the computational efficiency point of view. | es |
dc.description.sponsorship | Ministerio de Educación y Ciencia TIN2005-09345-C04-01 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Taylor and Francis | es |
dc.relation.ispartof | International Journal of Computer Mathematics, 83 (7), 593-611. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Computational efficiency | es |
dc.subject | Dissolution rules | es |
dc.subject | Membrane systems | es |
dc.title | Computational efficiency of dissolution rules in membrane systems | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | TIN2005-09345-C04-01 | es |
dc.relation.publisherversion | http://www.tandfonline.com/doi/abs/10.1080/00207160601065413 | es |
dc.identifier.doi | 10.1080/00207160601065413 | es |
dc.contributor.group | Universidad de Sevilla. TIC193 : Computación Natural | es |
idus.format.extent | 19 p. | es |
dc.journaltitle | International Journal of Computer Mathematics | es |
dc.publication.volumen | 83 | es |
dc.publication.issue | 7 | es |
dc.publication.initialPage | 593 | es |
dc.publication.endPage | 611 | es |
dc.contributor.funder | Ministerio de Educación y Ciencia (MEC). España | |