dc.creator | Valencia Cabrera, Luis | es |
dc.creator | Orellana Martín, David | es |
dc.creator | Martínez del Amor, Miguel Ángel | es |
dc.creator | Riscos Núñez, Agustín | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2017-12-21T10:40:19Z | |
dc.date.available | 2017-12-21T10:40:19Z | |
dc.date.issued | 2017 | |
dc.identifier.citation | Valencia Cabrera, L., Orellana Martín, D., Martínez del Amor, M.Á., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2017). Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards. En BWMC 2017: 15th Brainstorming Week on Membrane Computing (253-290), Sevilla, España: Fenix Editora. | |
dc.identifier.isbn | 978-84-946316-9-6 | es |
dc.identifier.uri | http://hdl.handle.net/11441/67921 | |
dc.description.abstract | Membrane computing is a computing paradigm providing a class of distributed
parallel computing devices of a biochemical type whose process units represent
biological membranes. In the cell-like basic model, a hierarchical membrane structure
formally described by a rooted tree is considered. It is well known that families of such
systems where the number of membranes can only decrease during a computation (for
instance by dissolving membranes), can only solve in polynomial time problems in class
P. P systems with active membranes is a variant where membranes play a central role in
their dynamics. In the seminal version, membranes have an electrical polarization (positive,
negative, or neutral) associated in any instant, and besides being dissolved, they can
also replicate by using division rules. These systems are computationally universal, that
is, equivalent in power to deterministic Turing machines, and computationally e fficient,
that is, able to solve computationally hard problems in polynomial time. If polarizations
in membranes are removed and dissolution rules are forbidden, then only problems in
class P can be solved in polynomial time by these systems (even in the case when division
rules for non-elementary membranes are permitted). In that framework it has been
shown that by considering minimal cooperation (left-hand side of such rules consists of
at most two symbols) and minimal production (only one object is produced by the application
of such rules) in object evolution rules, such systems provide e cient solutions to
NP{complete problems. In this paper, minimal cooperation and minimal production in
communication rules instead of object evolution rules is studied, and the computational
e fficiency of these systems is obtained in the case where division rules for non-elementary
membranes are permitted. | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Fenix Editora | es |
dc.relation.ispartof | BWMC 2017: 15th Brainstorming Week on Membrane Computing (2017), p 253-290 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane Computing | es |
dc.subject | Polarizationless P systems with active membranes | es |
dc.subject | Cooperative rules | es |
dc.subject | P versus NP problem | es |
dc.subject | SAT problem | es |
dc.title | Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards | 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.publisherversion | http://www.gcn.us.es/15bwmc_proceedings | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 37 | es |
dc.publication.initialPage | 253 | es |
dc.publication.endPage | 290 | es |
dc.eventtitle | BWMC 2017: 15th Brainstorming Week on Membrane Computing | es |
dc.eventinstitution | Sevilla, España | es |
dc.relation.publicationplace | Sevilla | es |