Repositorio de producción científica de la Universidad de Sevilla

Limits on P Systems with Proteins and Without Division

 

Advanced Search
 
Opened Access Limits on P Systems with Proteins and Without Division
Cites
Show item statistics
Icon
Export to
Author: Orellana Martín, David
Valencia Cabrera, Luis
Riscos Núñez, Agustín
Pérez Jiménez, Mario de Jesús
Department: Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Date: 2018
Published in: BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (2018), p 123-138
Document type: Presentation
Abstract: In the field of Membrane Computing, computational complexity theory has been widely studied trying to nd frontiers of efficiency by means of syntactic or semantical ingredients. The objective of this is to nd two kinds of systems, one non-efficient and another one, at least, presumably efficient, that is, that can solve NP-complete prob- lems in polynomial time, and adapt a solution of such a problem in the former. If it is possible, then P = NP. Several borderlines have been defi ned, and new characterizations of different types of membrane systems have been published. In this work, a certain type of P system, where proteins act as a supporting element for a rule to be red, is studied. In particular, while division rules, the abstraction of cellular mitosis is forbidden, only problems from class P can be solved, in contrast to the result obtained allowing them.
Cite: Orellana Martín, D., Valencia Cabrera, L., Riscos Núñez, A. y Pérez Jiménez, M.d.J. (2018). Limits on P Systems with Proteins and Without Division. En BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (123-138), Sevilla, España: Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática.
Size: 113.7Kb
Format: PDF

URI: https://hdl.handle.net/11441/84112

See editor´s version

This work is under a Creative Commons License: 
Atribución-NoComercial-CompartirIgual 4.0 Internacional

This item appears in the following Collection(s)