dc.creator | Díaz Pernil, Daniel | es |
dc.creator | Christinal, Hepzibah A. | es |
dc.creator | Gutiérrez Naranjo, Miguel Ángel | es |
dc.date.accessioned | 2016-12-07T10:55:02Z | |
dc.date.available | 2016-12-07T10:55:02Z | |
dc.date.issued | 2016 | |
dc.identifier.citation | Díaz Pernil, D., Christinal, H.A. y Gutiérrez Naranjo, M.Á. (2016). Solving the 3-COL Problem by Using Tissue P Systems without Environment and Proteins on Cells. En BWMC 2016 : 14th Brainstorming Week on Membrane Computing : Sevilla, E. T. S. de Ingeniería Informática, February 1-5 (163-172), Sevilla: Fénix. | |
dc.identifier.uri | http://hdl.handle.net/11441/49805 | |
dc.description.abstract | The 3-COL problem consists on deciding if the regions of a map can be
coloured with only three colors bearing in mind that two adjacent regions must be
coloured with di erent colors. It is a NP problem and it has been previously used in
complexity studies in membrane computing to check the ability of a model for solving
problems of such complexity class. Recently, tissue P systems with proteins on cells have
been presented and its ability to solve NP-problems has been proved, but it remained
as an open question to know if such model was still able to solve such problems if the
environment was removed. In this paper we provide an a rmative answer to this question
by showing a uniform family of tissue P systems without environment and with proteins
on cells which solves the 3-COL problem in linear time. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fénix | es |
dc.relation.ispartof | BWMC 2016 : 14th Brainstorming Week on Membrane Computing : Sevilla, E. T. S. de Ingeniería Informática, February 1-5 (2016), p 163-172 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Solving the 3-COL Problem by Using Tissue P Systems without Environment and Proteins on Cells | 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.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.publisherversion | http://www.gcn.us.es/files/14bwmc/163_dani_hepzi_miguel.pdf | es |
dc.contributor.group | Universidad de Sevilla. TIC193 : Computación Natural | es |
dc.contributor.group | Universidad de Sevilla. FQM296 : Topología Computacional y Matemática Aplicada | es |
idus.format.extent | 10 | es |
dc.publication.initialPage | 163 | es |
dc.publication.endPage | 172 | es |
dc.eventtitle | BWMC 2016 : 14th Brainstorming Week on Membrane Computing : Sevilla, E. T. S. de Ingeniería Informática, February 1-5 | es |
dc.eventinstitution | Sevilla | es |
dc.relation.publicationplace | Sevilla | es |
dc.identifier.idus | https://idus.us.es/xmlui/handle/11441/49805 | |