ORELLANA MARTÍN , David

P systems with active membranes is a widely studied framework within the field of Membrane Computing since the creation of the discipline. The abstraction of the structure and behavior of living cells is reflected in the tree-like hierarchy and the kinds of rules that can be used in these kinds of systems. Resembling the organization and...

No description

In 2005, Gh. Păun raised an interesting question concerning the role of electrical charges in P systems with active membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of polarization-less P systems with dissolution rules and division rules only for elementary membranes....

Many variants of P systems have the ability to generate an exponential number of membranes in linear time. This feature has been exploited to elaborate (theoretical) efficient solutions to NP-complete, or even harder, problems. A thorough review of the existent solutions shows the utilization of common techniques and procedures. The...

We model the problem of contour approximation using Hilbert's space lling curve, with a novel type of parallel array rewriting rules. We further use their pattern to introduce a special type of tissue P system, with novel features, among which is controlling their behavior with input. We propose some further developments.

From the creation of the field of Membrane Computing in 1998, several research lines havebeen opened. On the one hand, theoretical questions like the computational power and thecomputational efficiency of P systems have been studied. In this sense, several techniquesto demonstrate the ability of these systems to provide solutions to...

A widely studied field in the framework of membrane computing is computational complexity theory. While some types of P systems are only capable of efficiently solving problems from the class P, adding one or more syntactic or semantic ingredients to these membrane systems can give them the ability to efficiently solve presumably intractable...

In Membrane Computing, diferent variants of devices can be found by changing both syntactical and semantic ingredients. These devices are usually called membrane systems or P systems, and they recall the structure and behavior of living cells in the nature. In this sense, rules are introduced as a way for objects to interact with membranes,...

The factorization problem (given a natural number which is the product of two prime numbers, find its decomposition) is conjectured to be intractable and for that it has been used as the key to have secure current cryptosystems. Due to its relevance, this problem has been studied in various computational paradigms, in particular in...

P systems are computing devices based on sets of rules that dictate how they work. While some of these rules can change the objects within the system, other rules can even change the own structure, like creation rules. They have been used in cell-like membrane systems with active membranes to efficiently solve NP-complete problems. In this...

In the framework of membrane computing, several frontiers of e ciency have been found with respect to the resources that di erent families of P systems take to solve a decision problem. Each of these frontiers provides a new way to tackle the P versus NP problem. In this sense, optimal frontiers are needed in order to separate close variants...

P systems with active membranes are a class of computation models in the area ofmembrane computing, which are inspired from the mechanism by which chemicalsinteract and cross cell membranes. In this work, we consider a normal form of P systemswith active membranes, called cell-like P systems with polarizations and minimal rules,where rules are...

Spiking Neural P Systems (SNP) are well-established computing models that take inspiration from spikes between biological neurons; these models have been widely used for both theoretical studies and practical applications. Virus machines (VMs) are an emerging computing paradigm inspired by viral transmission and replication. In this work, a...

Cooperation is doubtless a critical ingredient of a computing model. This paper provides an overview on results showing how forbidding cooperation, or allowing it only a minimum degree, influences the computing power. In particular, we restrict ourselves to two types of cell-like membrane systems. On one hand, we analyze the efficiency of...

Complexity class DP is the class of "differences" of any two languages in NP. It verifies that NP[ co-NP DP PNP, where PNP is the second level of the polynomial hierarchy, specifically, it is the class of languages decidable by a deterministic polynomial-time Turing machine having access to an NP oracle. The unique sastifiability problem...

The (presumed) efficiency of computing models is expressed by means of their ability to solve (NP-complete) presumably intractable problems in an efficient way or not. The relevance of this kind of frontier lies in the fact that each of them provides a tool to attacking the P versus NP problem. In the framework of Membrane Computing, different...

The tape of a deterministic Turing machine contains an unbounded number of cells. Thanks to that, a single machine can solve decision problems with an infinite number of instances. Nevertheless, in the framework of membrane computing, traditionally a \solution" to an abstract decision problem consists of a family of membrane systems (where each...

A decision problem is one that has a yes/no answer, while a counting problem asks how many possible solutions exist associated with each instance. Every decision problem X has associated a counting problem, denoted by #X, in a natural way by replacing the question "is there a solution?" with "how many solutions are there?". Counting problems...

The search for new mechanisms and tools allowing us to tackle the famousPversusNPproblem from new perspectives is an important task, due to the relevance of that problem.The concept of efficiency of computing models is associated with the ability to solveintractable (in a classical sense) problems in polynomial time. Assuming that P =NP, that...

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...

Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such...

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...

Methods based on Rapidly-exploring Random Trees (RRTs) have been in use in robotics to solve motion planning problems for nearly two decades. On the other hand, in the membrane computing framework, models based on Enzymatic Numerical P systems (ENPS) have been applied to robot controllers. These controllers handle the power of motors...

Over the last few years, a new methodology to address the P versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). .ese borderlines...

Cell-like P systems with symport/antiport rules are computing models inspired by theconservation law, in the sense that they compute by changing the places of objectswith respect to the membranes, and not by changing the objects themselves. In thiswork, a variant of these kinds of membrane systems, called cell-like P systems...