Show simple item record

dc.creatorPérez Jiménez, Mario de Jesús
dc.creatorSosík, Petr
dc.date.accessioned2016-02-04T11:57:01Z
dc.date.available2016-02-04T11:57:01Z
dc.date.issued2012
dc.identifier.isbn978-84-940056-6-4es
dc.identifier.urihttp://hdl.handle.net/11441/34096
dc.description.abstractCell fission process consists of the division of a cell into two new cells such that the contents of the initial cell is distributed between the newly created cells. This process is modelled by a new kind of cell separation rules in the framework of Membrane Computing. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. These models are able to create an exponential workspace, expressed in terms of the number of cells, in linear time. On the one hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. On the other hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 1. Thus, in the framework of tissue P systems with cell separation, and assuming that P ̸= NP, a first frontier between efficiency and non-efficiency is obtained when passing from communication rules with length 1 to communication rules with length at most 8. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Hence, we provide a new tractability borderline: passing from 1 to 3 amounts to passing from non–efficiency to efficiency, assuming that P ̸= NP.es
dc.description.sponsorshipMinisterio de Ciencia e Innovación TIN2009-13192
dc.description.sponsorshipJunta de Andalucía P08 – TIC 04200
dc.formatapplication/pdfes
dc.language.isoenges
dc.publisherFénix Editoraes
dc.relation.ispartofProceedings of the Tenth Brainstorming Week on Membrane Computing, (2)105-140. Sevilla, E.T.S. de Ingeniería Informática, 30 de Enero-3 de Febrero, 2012,es
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleImproving the Efficiency of Tissue P Systems with Cell Separationes
dc.typeinfo:eu-repo/semantics/conferenceObjectes
dc.type.versioninfo:eu-repo/semantics/publishedVersiones
dc.rights.accessrightsinfo:eu-repo/semantics/openAccesses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificiales
dc.relation.projectIDTIN2009-13192
dc.relation.projectIDP08 – TIC 04200
dc.contributor.groupUniversidad de Sevilla. TIC193: Computación Natural
dc.identifier.idushttps://idus.us.es/xmlui/handle/11441/34096
dc.contributor.funderMinisterio de Ciencia e Innovación (MICIN). España
dc.contributor.funderJunta de Andalucía

FilesSizeFormatViewDescription
mario-sosik.pdf217.8KbIcon   [PDF] View/Open  

This item appears in the following collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
Except where otherwise noted, this item's license is described as: Attribution-NonCommercial-NoDerivatives 4.0 Internacional