dc.creator | Pan, Linqiang | es |
dc.creator | Song, Bosheng | es |
dc.creator | Valencia Cabrera, Luis | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2019-05-30T09:58:36Z | |
dc.date.available | 2019-05-30T09:58:36Z | |
dc.date.issued | 2018 | |
dc.identifier.citation | Pan, L., Song, B., Valencia Cabrera, L. y Pérez Jiménez, M.d.J. (2018). The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules. Complexity, 2018 (Article ID 3745210) | |
dc.identifier.issn | 1076-2787 | es |
dc.identifier.uri | https://hdl.handle.net/11441/87022 | |
dc.description.abstract | Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical
systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when
moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in
the framework of tissue P systems with evolutional communication rules.The computational complexity of this kind of P systems
is investigated. It is proved that only problems in class P can be efficiently solved by tissue P systems with cell separation with
evolutional communication rules of length at most (��, 1), for each natural number �� ≥ 1. In the case where that length is upper
bounded by (3, 2), a polynomial time solution to the SAT problem is provided, hence, assuming that P ̸= NP a new boundary
between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new
simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution
to the SAT problem. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Hindawi | es |
dc.relation.ispartof | Complexity, 2018 (Article ID 3745210) | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | 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.publisherversion | https://www.hindawi.com/journals/complexity/2018/3745210/ | es |
dc.identifier.doi | 10.1155/2018/3745210 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 22 | es |
dc.journaltitle | Complexity | es |
dc.publication.volumen | 2018 | es |
dc.publication.issue | Article ID 3745210 | es |