Mostrar el registro sencillo del ítem
Ponencia
Characterizing Tractability by Tissue-Like P Systems
dc.creator | Gutiérrez Escudero, Rosa | |
dc.creator | Pérez Jiménez, Mario de Jesús | |
dc.creator | Rius Font, Miquel | |
dc.date.accessioned | 2016-03-21T09:44:34Z | |
dc.date.available | 2016-03-21T09:44:34Z | |
dc.date.issued | 2009 | |
dc.identifier.isbn | 9788461328369 | es |
dc.identifier.uri | http://hdl.handle.net/11441/38863 | |
dc.description.abstract | In the framework of cell–like membrane systems it is well known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP–complete problems. Nonetheless, it may be sufficient to create an exponential number of membranes in polynomial time. In the framework of recognizer polarizationless P systems with active membranes, the construction of an exponential workspace expressed in terms of number of membranes and objects may not suffice to efficiently solve computationally hard problems. In this paper we study the computational efficiency of recognizer tissue P systems with communication (symport/antiport) rules and division rules. Some results have been already obtained in this direction: (a) using communication rules and forbidding division rules, only tractable problems can be efficiently solved; (b) using communication rules with length three and division rules, NP–complete problems can be efficiently solved. In this paper we show that the allowed length of communication rules plays a relevant role from the efficiency point of view of the systems. | es |
dc.description.sponsorship | Ministerio de Educación y Ciencia TIN2006–13425 | |
dc.description.sponsorship | Junta de Andalucía P08-TIC-04200 | |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix Editora | es |
dc.relation.ispartof | Proceedings of the Seventh Brainstorming Week on Membrane Computing, vol.I, 169-180. Sevilla, E.T.S. de Ingeniería Informática, 2-6 de Febrero, 2009 | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Characterizing Tractability by Tissue-Like P Systems | es |
dc.type | info:eu-repo/semantics/conferenceObject | es |
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 | TIN2006–13425 | |
dc.relation.projectID | P08-TIC-04200 | |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/38863 | |
dc.contributor.funder | Ministerio de Educación y Ciencia (MEC). España | |
dc.contributor.funder | Junta de Andalucía |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
19_MarioTissue.pdf | 158.2Kb | [PDF] | Ver/ | |