Mostrar el registro sencillo del ítem
Ponencia
Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation
dc.creator | Valencia Cabrera, Luis | |
dc.creator | Song, Bosheng | |
dc.creator | Macías Ramos, Luis Felipe | |
dc.creator | Pan, Linqiang | |
dc.creator | Riscos Núñez, Agustín | |
dc.creator | Pérez Jiménez, Mario de Jesús | |
dc.date.accessioned | 2016-01-22T08:47:41Z | |
dc.date.available | 2016-01-22T08:47:41Z | |
dc.date.issued | 2015 | |
dc.identifier.isbn | 978-84-944366-2-8 | es |
dc.identifier.uri | http://hdl.handle.net/11441/33124 | |
dc.description.abstract | Membrane ssion is a process by which a biological membrane is split into two new ones in such a way that the contents of the initial membrane is separated and distributed between the new membranes. Inspired by this biological phenomenon, membrane separation rules were considered in membrane computing. In this paper we deal with celllike P systems with membrane separation rules that use symport/antiport rules (such systems compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves) as communication rules. Speci cally we study a lower bound on the length of communication rules with respect to the computational e ciency of such kind of membrane systems; that is, their ability to solve computationally hard problems in polynomial time by trading space for time. The main result of this paper is the following: communication rules involving at most three objects is enough to achieve the computational e ciency of P systems with membrane separation. Thus, a polynomial time solution to SAT problem is provided in this computing framework. It is known that only problems in P can be solved in polynomial time by using minimal cooperation in communication rules and membrane separation, so the lower bound of the e ciency obtained is an optimal bound. | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad TIN2012-37434 | |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 325-370. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2015, | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Computational Efficiency of P Systems with Symport/Antiport Rules and Membrane Separation | es |
dc.type | info:eu-repo/semantics/conferenceObject | 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.projectID | info:eu-repo/grantAgreement/MINECO/TIN2012-37434 | |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/33124 | |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
325_comp-eff-sym-ant-sep.pdf | 475.0Kb | [PDF] | Ver/ | |