dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.creator | Rius Font, Miquel | es |
dc.creator | Romero Campero, Francisco José | es |
dc.date.accessioned | 2018-11-02T08:31:45Z | |
dc.date.available | 2018-11-02T08:31:45Z | |
dc.date.issued | 2013 | |
dc.identifier.citation | Pérez Jiménez, M.d.J., Riscos Núñez, A., Rius Font, M. y Romero Campero, F.J. (2013). A polynomial alternative to unbounded environment for tissue P systems with cell division. International Journal of Computer Mathematics, 90 (4), 760-775. | |
dc.identifier.issn | 0020-7160 | es |
dc.identifier.uri | https://hdl.handle.net/11441/79751 | |
dc.description.abstract | The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear
in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a
distinguished place of the system, called the environment. Such potentially infinite supply of objects seems
an unfair tool when designing efficient solutions to computationally hard problems in the framework of
membrane computing, by performing a space–time trade-off. This paper deals with computational aspects
of tissue P systems with cell division where there is no environment having the property mentioned above.
Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell
division and with or without environment are actually identical. As a consequence, we conclude that it is
not necessary to have infinitely many copies of some objects in the initial configuration in order to solve
NP–complete problems in an efficient way. | es |
dc.description.sponsorship | Ministerio de Ciencia e Innovación TIN2009–13192 | es |
dc.description.sponsorship | Junta de Andalucía P08-TIC-04200 | 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, 90 (4), 760-775. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane Computing | es |
dc.subject | Tissue P systems | es |
dc.subject | Cell division | es |
dc.subject | Environment of a tissue | es |
dc.subject | Computational complexity | es |
dc.title | A polynomial alternative to unbounded environment for tissue P systems with cell division | 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 | TIN2009–13192 | es |
dc.relation.projectID | P08-TIC-04200 | es |
dc.relation.publisherversion | https://www.tandfonline.com/doi/abs/10.1080/00207160.2012.748898 | es |
dc.identifier.doi | 10.1080/00207160.2012.748898 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 16 | es |
dc.journaltitle | International Journal of Computer Mathematics | es |
dc.publication.volumen | 90 | es |
dc.publication.issue | 4 | es |
dc.publication.initialPage | 760 | es |
dc.publication.endPage | 775 | es |
dc.identifier.sisius | 20430830 | es |
dc.contributor.funder | Ministerio de Ciencia e Innovación (MICIN). España | |
dc.contributor.funder | Junta de Andalucía | |