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

A polynomial alternative to unbounded environment for tissue P systems with cell division

 

Advanced Search
 

Show simple item record

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

This item appears in the following Collection(s)

Show simple item record