9 results on '"Riscos-Núñez, Agustín"'
Search Results
2. When object production tunes the efficiency of membrane systems
- Author
-
Orellana Martín, David, Martínez del Amor, Miguel Ángel, Pérez Hurtado de Mendoza, Ignacio, Riscos Núñez, Agustín, Valencia Cabrera, Luis, Pérez Jiménez, Mario de Jesús, Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial, Universidad de Sevilla. TIC193: Computación Natural, Ministerio de Economía y Competitividad (MINECO). España, and National Natural Science Foundation of China
- Subjects
Computational complexity ,Minimal cooperation ,Membrane Computing ,Active membranes - Abstract
Psystems with active membranes is one of the most studied models within the field ofMembrane Computing. Simulating the organization and behavior of the living cells througha tree-like structure and abstracting the mechanisms that help the cell to keep alive intorules (evolution, communication, dissolution and division rules), they have been used tosolve several computationally hard problems. We are dealing with non-cooperative systemshere, that is, the number of reactives in a rule is always one. Even then, it has been proventhat problems from the classPSPACEcan be solved, so in order to acquire a minimal modelthat can solve computationally hard problems, polarizations are removed. In this paper wefind the relevance of the length of the right-hand side of the rule, being necessary whenusing separation rules and being irrelevant when division rules are used, improving somesolutions previously presented, restricting the right-hand side of the rules, obtaining newfrontiers of efficiency in this framework. The state of the art of these systems is presentedin a graphical way. Ministerio de Economía y Competitividad TIN2017-89842-P National Natural Science Foundation of China No. 61320106005
- Published
- 2020
3. A fast P system for finding a balanced 2-partition
- Author
-
Gutiérrez-Naranjo, Miguel A., Pérez-Jiménez, Mario J., and Riscos-Núñez, Agustín
- Published
- 2005
- Full Text
- View/download PDF
4. Limits on P Systems with Proteins and Without Division
- Author
-
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, Universidad de Sevilla. TIC193: Computación Natural, Ministerio de Economía y Competitividad (MINECO). España, and National Natural Science Foundation of China
- Subjects
Computational complexity theory ,Proteins ,Membrane Computing ,Active membranes - 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. Ministerio de Economía y Competitividad TIN2017-89842-P National Natural Science Foundation of China No 61320106005
- Published
- 2018
5. Polarizationless P Systems with Active Membranes: Computational Complexity Aspects
- Author
-
Valencia Cabrera, Luis, Orellana Martín, David, Martínez del Amor, Miguel Ángel, 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, Universidad de Sevilla. TIC193 : Computación Natural, and National Natural Science Foundation of China
- Subjects
Computational complexity ,the P versus NP problem ,010201 computation theory & mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Membrane computing ,Minimal cooperation ,Mitosis ,020201 artificial intelligence & image processing ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Active membranes - Abstract
P systems with active membranes, in their classical definition, make use of non-cooperative rules only. However, it is well known that in living cells, proteins interact %between themselves among them yielding new products. Inspired by this biological phenomenon, the previous framework is reformulated in this paper, allowing cooperation in object evolution rules, while removing electrical charges associated with membranes. More precisely, minimal cooperation in object evolution rules is incorporated in polarizationless P systems with active membranes. In this paper, the term ``minimal'' means that the left-hand side of such rules consists of at most two symbols, and its length is greater than or equal to the corresponding right-hand side. The computational efficiency of this kind of P systems is studied by providing a uniform polynomial-time solution to {\tt SAT} problem in such manner that only division rules for elementary membranes are used and dissolution rules are forbidden. Bearing in mind that only tractable problems can be efficiently solved by families of polarizationless P systems with active membranes and without dissolution rules, passing from non-cooperation to minimal cooperation in object evolution rules amounts passing from non-efficiency to efficiency in this framework. This frontier of efficiency provides, as any other borderline does, a possible way to address the {\bf P} versus {\bf NP} problem., Journal of Automata, Languages and Combinatorics, Volume 21, Numbers 1-2, 2016, 107-123
- Published
- 2016
6. Minimal cooperation in polarizationless P systems with active membranes
- Author
-
Valencia Cabrera, Luis, Orellana Martín, David, 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, and Universidad de Sevilla. TIC193 : Computación Natural
- Subjects
Computational Complexity ,The P versus NP problem ,Membrane computing ,Minimal cooperation ,Mitosis ,Active membranes - Abstract
P systems with active membranes is a well developed framework in the eld of Membrane Computing. Using evolution, communication, dissolution and division rules, we know that some kinds of problems can be solved by those systems, but taking into account which ingredients are used. All these rules are inspired by the behavior of living cells, who \compute" with their proteins in order to obtain energy, create components, send information to other cells, kill themselves (in a process called apoptosis), and so on. But there are other behaviors not captured in this framework. As mitosis is simulated by division rules (for elementary and non-elementary membranes), meiosis, that is, membrane ssion inspiration is captured in separation rules. It di ers from the rst in the sense of duplication of the objects (that is, in division rules, we duplicate the objects not involved in the rule, meanwhile in separation rules we divide the content of the original membrane into the new membranes created). Evolution rules simulate the transformation of components in membranes, but it is well known that elements interact with another ones in order to obtain new components. Cooperation in evolution rules is considered. More speci cally, minimal cooperation (in the sense that only two objects can interact in order to create one or two objects)
- Published
- 2016
7. ON A PARTIAL AFFIRMATIVE ANSWER FOR A PĂUN'S CONJECTURE.
- Author
-
PÉREZ-HURTADO, IGNACIO, PÉREZ-JIMÉNEZ, MARIO J., RISCOS-NÚÑEZ, AGUSTÍN, GUTIÉRREZ-NARANJO, MIGUEL A., RIUS-FONT, MIQUEL, and Mitrana, Victor
- Subjects
COMPUTER systems ,BIOLOGICAL membranes ,COMPUTERS in biology ,BIOLOGICAL evolution ,PROBLEM solving ,COMPUTATIONAL complexity ,PROOF theory - Abstract
At the beginning of 2005, Gheorghe Păun formulated a conjecture stating that in the framework of recognizer P systems with active membranes (evolution rules, communication rules, dissolution rules and division rules for elementary membranes), polarizations cannot be avoided in order to solve computationally hard problems efficiently (assuming that P ≠ NP). At the middle of 2005, a partial positive answer was given, proving that the conjecture holds if dissolution rules are forbidden. In this paper we give a detailed and complete proof of this result modifying slightly the notion of dependency graph associated with recognizer P systems. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
8. When object production tunes the efficiency of membrane systems.
- Author
-
Orellana-Martín, David, Martínez-del-Amor, Miguel Á., Pérez-Hurtado, Ignacio, Riscos-Núñez, Agustín, Valencia-Cabrera, Luis, and Pérez-Jiménez, Mario J.
- Subjects
- *
ORGANIZATIONAL behavior , *COMPUTATIONAL complexity - Abstract
P systems with active membranes is one of the most studied models within the field of Membrane Computing. Simulating the organization and behavior of the living cells through a tree-like structure and abstracting the mechanisms that help the cell to keep alive into rules (evolution, communication, dissolution and division rules), they have been used to solve several computationally hard problems. We are dealing with non-cooperative systems here, that is, the number of reactives in a rule is always one. Even then, it has been proven that problems from the class PSPACE can be solved, so in order to acquire a minimal model that can solve computationally hard problems, polarizations are removed. In this paper we find the relevance of the length of the right-hand side of the rule, being necessary when using separation rules and being irrelevant when division rules are used, improving some solutions previously presented, restricting the right-hand side of the rules, obtaining new frontiers of efficiency in this framework. The state of the art of these systems is presented in a graphical way. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
9. From distribution to replication in cooperative systems with active membranes: A frontier of the efficiency.
- Author
-
Valencia-Cabrera, Luis, Orellana-Martín, David, Martínez-del-Amor, Miguel Á., Riscos-Núñez, Agustín, and Pérez-Jiménez, Mario J.
- Subjects
- *
COMMUNICATION , *MEIOSIS , *MITOSIS , *CELL membranes , *CELL division - Abstract
P systems with active membranes use evolution, communication, dissolution and division (or separation) rules. They do not use cooperation neither priorities, but they have electrical charges associated with membranes, which can be modified by rule applications. The inspiration comes from the behaviour of living cells, who “compute” with their proteins in order to obtain energy, create components, send information to other cells, kill themselves (in a process called apoptosis ), and so on. In these models, mitosis is simulated by division rules (for elementary and non-elementary membranes) and meiosis , that is, membrane fission inspiration, is captured in separation rules. The parent's objects are replicated into both child membranes when a division occurs, while in the case of separation, objects are distributed (according to a prefixed partition). In both cases, active membranes have been proved to be too powerful for solving computationally hard problems in an efficient way. Due to this, polarizationless P systems with active membranes have been widely studied from a complexity point of view. Evolution rules simulate the transformation of components in membranes, but it is well known that in Biology elements interact with each other in order to obtain new components. In this paper, (restricted) cooperation in object evolution rules is considered, and the efficiency of the corresponding models is studied. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.