Jornadas y Congresos US

URI permanente para esta comunidadhttps://hdl.handle.net/11441/30105

Esta comunidad recoge las actas de los congresos celebrados en la Universidad de Sevilla u organizados por la misma.

This community collects the acts of the congresses held at the Universidad de Sevilla or organized by it.

Examinar

Mostrando 1 - 2 de 2

Limits on P Systems with Proteins and Without Division
(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Orellana Martín, David; Valencia Cabrera, Luis; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; National Natural Science Foundation of China; Universidad de Sevilla. TIC193: Computación Natural
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.
Narrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation
(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018) Orellana Martín, David; Valencia Cabrera, Luis; Song, Bosheng; Pan, Linqiang; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Economía y Competitividad (MINECO). España; National Natural Science Foundation of China; Universidad de Sevilla. TIC193: Computación Natural
In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important way to tackle the P versus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumably efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the SAT problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects.

Examinar

Examinando Jornadas y Congresos US por Agencia financiadora "National Natural Science Foundation of China"