Show simple item record


dc.creatorValencia Cabrera, Luises
dc.creatorOrellana Martín, Davides
dc.creatorMartínez del Amor, Miguel Ángeles
dc.creatorRiscos Núñez, Agustínes
dc.creatorPérez Jiménez, Mario de Jesúses
dc.identifier.citationValencia 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 Inwards. En BWMC 2017: 15th Brainstorming Week on Membrane Computing (215-252), Sevilla, España: Fenix Editora.
dc.description.abstractMembrane 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 effi cient, 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 effi 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
dc.publisherFenix Editoraes
dc.relation.ispartofBWMC 2017: 15th Brainstorming Week on Membrane Computing (2017), p 215-252
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.subjectMembrane Computinges
dc.subjectPolarizationless P systems with active membraneses
dc.subjectCooperative ruleses
dc.subjectP versus NP problemes
dc.subjectSAT problemes
dc.titleRestricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Inwardses
dc.contributor.affiliationUniversidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificiales
dc.contributor.groupUniversidad de Sevilla. TIC193: Computación Naturales
dc.eventtitleBWMC 2017: 15th Brainstorming Week on Membrane Computinges
dc.eventinstitutionSevilla, Españaes

215_Inwards.pdf492.0KbIcon   [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