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

Computational efficiency of dissolution rules in membrane systems

 

Advanced Search
 

Show simple item record

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
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
Size: 194.9Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record