Narrow Results

In the framework of membrane computing, several interesting results concerning frontiers of efficiency between the complexity classes P and NP have been found by using different ingredients. One of the main characteristics of cell-like membrane systems is their rooted tree-like structure, where a natural parent-children membrane relationship exists, and objects can travel through the membranes. Separation rules are used as a method to obtain an exponential workspace in terms of membranes in polynomial time. Inspired by cell meiosis, objects from the original membrane are distributed between the two new membranes. In this work, P systems with evolutional symport/antiport rules and separation rules are used to give a solution to SAT, a well known NP-complete problem. One of the advantages of this solution is the use of the environment as a passive agent.

There are presented certain membrane systems for computing the inverse of one-way functions in a polynomial time. The membrane systems are derived from some mathematical models of natural processes investigated in biochemistry and they have been introduced by Gh. Păun.

In this paper we introduce a fuzzy version of symport/antiport membrane systems. Our fuzzy membrane systems handle possibly inexact copies of reactives and their rules are endowed with threshold functions that determine whether a rule can be applied or not to a given set of objects, depending of the degree of accuracy of these objects to the reactives specified in the rule. We prove that these fuzzy membrane systems generate exactly the recursively enumerable finite-valued fuzzy subsets of ℕ.

Based on a quite general definition of P systems where the rules are applied in a sequential way (and not in the maximally parallel way as it usually happens in most models of P systems considered so far in the literature), we investigate the generative power of various models of such P systems working in the sequential mode on arrays and strings, respectively. P systems working in the sequential mode on arrays/strings without priority relations for the rules reveal the same computational power as the corresponding matrix grammars without appearance checking working on arrays/strings. For obtaining the computational power of matrix grammars with appearance checking, priority relations for the rules (as one of many other possible additional features) are needed.

We consider tissue P systems with symport/antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, we need at most six (seven when allowing only one channel between a cell and the environment) cells to generate any recursively enumerable set of natural numbers. On the other hand, with only one cell we can only generate regular sets when using one channel with the environment, whereas one cell with two channels between the cell and the environment obtains computational completeness with five symbols. Between these extreme cases of one symbol and one cell, respectively, there seems to be a trade-off between the number of cells and the number of symbols. For example, for the case of tissue P systems with two channels between a cell and the environment we show that computational completeness can be obtained with two cells and three symbols as well as with three cells and two symbols, respectively. Moreover, we also show that some variants of tissue P systems characterize the families of finite or regular sets of natural numbers.

Some recent types of membrane systems have shown their potential in the modelling of specific processes governing biological cell behavior. These models represent the cell as a huge and complex dynamical system in which quantitative aspects, such as biochemical concentrations, must be related to the discrete informational nature of the DNA and to the function of the organelles living in the cytosol. In an effort to compute dynamical (especially oscillatory) phenomena—so far mostly treated using differential mathematical tools—by means of rewriting rules, we have enriched a known family of membrane systems (P systems), with rules that are applied proportionally to the values expressed by real functions called reaction maps. Such maps are designed to model the dynamic behavior of a biochemical phenomenon and their formalization is best worked out inside a family of P systems called PB systems. The overall rule activity is controlled by an algorithm that guarantees the system to evolve consistently with the available resources (i.e., objects). Though radically different, PB systems with reaction maps exhibit very interesting, often similar dynamic behavior as compared to systems of differential equations. Successful simulations of the Lotka-Volterra population dynamics, the Brusselator, and the Protein Kinase C activation foster potential applications of these systems in computational systems biology.

Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by – and make evolve – multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing; all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.

The purpose of this paper is twofold. On one hand, we introduce the concept of P system with dynamic communication graphs in its full generality, independent of applications. On the other hand, we illustrate one application of it to the simulation of a class of parallel architectures. In this last direction we extend previous work concerned with the simulation of particular architectures.

Current P systems which solve NP–complete numerical problems represent the instances of the problems in unary notation. However, in classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances generally corresponds to simplify the problem. In this paper we show that, when working with P systems, we can assume without loss of generality that instances are expressed in binary notation. More precisely, we propose a simple method to encode binary numbers using multisets, and a family of P systems which transforms such multisets into the usual unary notation. Such a family could thus be composed with the unary P systems currently proposed in the literature to obtain (uniform) families of P systems which solve NP–complete numerical problems with instances encoded in binary notation.

We introduce also a framework which can be used to design uniform families of P systems which solve NP–complete problems (both numerical and non-numerical) working directly on binary encoded instances, i.e., without first transforming them to unary notation. We illustrate our framework by designing a family of P systems which solves the 3-SAT problem. Next, we discuss the modifications needed to obtain a family of P systems which solves the PARTITION numerical problem.

The interconnections between membrane computing [9,11] and Gandy's principles for mechanisms in [3] are discussed. The embedding of the classes of hereditary finite sets (used to formulate Gandy's principles) into the class of abstract membrane systems is shown. A concept of a hereditary finite multiset is introduced as a special case of hereditary finite sets and then a representation of finite abstract membrane systems by hereditary finite multisets is presented. In this framework, a counterpart of the idea of reassemblance of hereditary finite sets is obtained for membrane systems.

We continue here the study of the recently introduced spiking neural P systems, which mimic the way that neurons communicate with each other by means of short electrical impulses, identical in shape (voltage), but emitted at precise moments of time. The sequence of moments when a neuron emits a spike is called the spike train (of this neuron); by designating one neuron as the output neuron of a spiking neural P system II, one obtains a spike train of II. Given a specific way of assigning sets of numbers to spike trains of II, we obtain sets of numbers computed by II. In this way, spiking neural P systems become number computing devices. We consider a number of ways to assign (code) sets of numbers to (by) spike trains, and prove then computational completeness: the computed sets of numbers are exactly Turing computable sets. When the number of spikes present in the system is bounded, a characterization of semilinear sets of numbers is obtained. A number of research problems is also formulated.

Spiking neural P systems were introduced in the end of the year 2005, in the aim of incorporating in membrane computing the idea of working with unique objects ("spikes"), encoding the information in the time elapsed between consecutive spikes sent from a cell/neuron to another cell/neuron. More than one dozen of papers where written in the meantime, clarifying many of the basic properties of these devices, especially related to their computing power.

The present paper quickly surveys the basic ideas and the basic results, presenting a complete to-date bibliography, and also giving a completing result related to the normal forms possible for spiking neural P systems: we prove that the indegree of such systems (the maximal number of incoming synapses of neurons) can be bounded by 2 without losing the computational completeness.

A series of research topics and open problems are formulated.

We continue the study of the spiking neural P systems considered as transducers of binary strings or binary infinite sequences, and we investigate their ability to compute morphisms. The class of computed morphisms is rather restricted: length preserving or erasing, and the so-called 2-block morphisms can be computed; however, non-erasing non-length-preserving morphisms cannot be computed.

The purpose of this paper is to present various algebraic views of multisets, and certain connections between the theory of multisets (with multiplicities in the semiring of positive integers) and natural computing, in particular membrane and DNA computing. We introduce a Gödel encoding of multisets, and find some results regarding this encoding together with new connections and interpretations. We also introduce the norm of a multiset and we find some relationships between multiset theory and number theory.

We use distributed labeled transition systems and their modal logics in order to compare the concurrency degrees of the P systems and their encoding as rewrite theories in rewriting logic. We show that the maximal concurrency given by the maximal parallel rewriting semantics of the P systems can be expressed in rewriting logic only by interleaving semantics. The maximal concurrency of the membrane interactions is only partially captured.

Ramsey numbers deal with conditions when a combinatorial object necessarily contains some smaller given objects. It is well known that it is very difficult to obtain the values of Ramsey numbers. In this work, a theoretical chemical/biological solution is presented in terms of membrane computing for the decision version of Ramsey number problem, that is, to decide whether an integer n is the value of Ramsey number R(k, l), where k and l are integers.

We prove that recognizer P systems with active membranes using polynomial space characterize the complexity class PSPACE. This result holds for both confluent and nonconfluent systems, and independently of the use of membrane division rules.

The quadratic assignment problem (QAP) is one of the fundamental combinatorial optimization problems, which models many real-life problems. However, it is considered as one of the most difficult NP-hard problems, which means that no polynomial-time algorithm is known to solve this intractable problem effectively. Even small instances of QAP may require vast computation time. In this work, a uniform cellular solution to QAP is proposed in the framework of membrane computing by using a family of recognizer tissue P systems with cell division. In the design of the solution, we encode the given instances in binary notations. The paper can be considered as a contribution to the study of considering a binary encoding of the information in P systems.

This paper discusses research frontiers of membrane computing by presenting current open problems and research topics, together with the relevant background and motivation.

Membrane systems (also called P systems) refer to the computing models abstracted from the structure and the functioning of the living cell as well as from the cooperation of cells in tissues, organs, and other populations of cells. Spiking neural P systems (SNPS) are a class of distributed and parallel computing models that incorporate the idea of spiking neurons into P systems. To attain the solution of optimization problems, P systems are used to properly organize evolutionary operators of heuristic approaches, which are named as membrane-inspired evolutionary algorithms (MIEAs). This paper proposes a novel way to design a P system for directly obtaining the approximate solutions of combinatorial optimization problems without the aid of evolutionary operators like in the case of MIEAs. To this aim, an extended spiking neural P system (ESNPS) has been proposed by introducing the probabilistic selection of evolution rules and multi-neurons output and a family of ESNPS, called optimization spiking neural P system (OSNPS), are further designed through introducing a guider to adaptively adjust rule probabilities to approximately solve combinatorial optimization problems. Extensive experiments on knapsack problems have been reported to experimentally prove the viability and effectiveness of the proposed neural system.