P systems with energy accounting ∗

We consider P systems where each evolution rule “Produces” or “Consumes” some quantity of energy, in amounts which are expressed as integer numbers. In each moment and in each membrane the total energy involved in an evolution step should be positive, but if “Soo much” energy is present in a membrane, then the membrane will be destroyed (dissolved). We show that this feature is rather powerful. In the case of multisets of symbol-objects we find that systems with two membranes and arbitrary energy associated with rules, or with arbitrarily many membranes and a bounded energy associated with rules characterize the recursively enumerable sets of vectors of natural numbers (catalysts and priorities are used). In the case of string-objects we have only proved that the recursively enumerable languages can be generated by systems with arbitrarily many membranes and bounded energy; when bounding the number of membranes and leaving free the quantity of energy associated with each rule we have only generated all matrix languages. Several research topics are also pointed out.     

Computationally universal P systems without priorities: two catalysts are sufficient

The original model of P systems with symbol objects introduced by Păun was shown to be computationally universal, provided that catalysts and priorities of rules are used. By reduction via register machines Sosík and Freund proved that the priorities may be omitted from the model without loss of computational power. Freund, Oswald, and Sosík considered several variants of P systems with catalysts (but without priorities) and investigated the number of catalysts needed for these specific variants to be computationally universal. It was shown that for the classic model of P systems with the minimal number of two membranes the number of catalysts can be reduced from six to five; using the idea of final states the number of catalysts could even be reduced to four. In this paper we are able to reduce the number of catalysts again: two catalysts are already sufficient. For extended P systems we even need only one membrane and two catalysts. For the (purely) catalytic systems considered by Ibarra only three catalysts are already enough.     

Asynchronous spiking neural P systems

We consider here spiking neural P systems with a non-synchronized (i.e., asynchronous) use of rules: in any step, a neuron can apply or not apply its rules which are enabled by the number of spikes it contains (further spikes can come, thus changing the rules enabled in the next step). Because the time between two firings of the output neuron is now irrelevant, the result of a computation is the number of spikes sent out by the system, not the distance between certain spikes leaving the system. The additional non-determinism introduced in the functioning of the system by the non-synchronization is proved not to decrease the computing power in the case of using extended rules (several spikes can be produced by a rule). That is, we obtain again the equivalence with Turing machines (interpreted as generators of sets of (vectors of) numbers). However, this problem remains open for the case of standard spiking neural P systems, whose rules can only produce one spike. On the other hand we prove that asynchronous systems, with extended rules, and where each neuron is either bounded or unbounded, are not computationally complete.For these systems, the configuration reachability, membership (in terms of generated vectors), emptiness, infiniteness, and disjointness problems are shown to be decidable. However, containment and equivalence are undecidable.     

P Systems with Global Rules

We contribute to the vivid area of membrane computing (P systems) by considering the case when the same evolution rules are valid in all regions of a system. Such a P system is called with global rules . We consider the case of string-objects, with the evolution rules based on splicing and by rewriting. Universality results are proved for both types of systems. For splicing we also try to minimize the diameter of the used rules, while for rewriting systems we improve a result from the literature, proving that two membranes suffice for simulating Turing machines.     

On generalized communicating P systems with minimal interaction rules

Generalized communicating P systems are purely communicating tissue-like membrane systems with communication rules which allow the movement of only pairs of objects. In this paper, we study the power of these systems in the case of eight restricted variants of communication rules. We show that seven of these restrictions lead to computational completeness, while using the remaining one the systems are able to compute only finite singletons of non-negative integers. The obtained results complete the investigations of the computational power of generalized communicating P systems and provide further examples for simple architectures with simple functioning rules which are as powerful as Turing machines.     

P systems with active membranes: trading time for space

We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.     

Notes on spiking neural P systems and finite automata

Spiking neural P systems (in short, SN P systems) are membrane computing models inspired by the pulse coding of information in biological neurons. SN P systems with standard rules have neurons that emit at most one spike (the pulse) each step, and have either an input or output neuron connected to the environment. A variant known as SN P modules generalize SN P systems by using extended rules (more than one spike can be emitted each step) and a set of input and output neurons. In this work we continue relating SN P modules and finite automata. In particular, we amend and improve previous constructions for the simulatons of deterministic finite automata and state transducers. Our improvements reduce the number of neurons from three down to one, so our results are optimal. We also simulate finite automata with output, and we use these simulations to generate automatic sequences.     

Computing using signals: from cells to P systems

In cell biology a fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computation is controlled by signals which move across the regions. In particular, we consider signals-based P systems where the symbol-objects cannot be moved and the evolution rules can be activated/inactivated using a finite number of signals (signal-promoters) moved across the membranes; differently from standard P systems using promoters, in our case signal-promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst and a bounded number of signal-promoters. Also results concerning signals-based P systems using non cooperative rules together with several open problems are presented.     

Membrane computing with transport and embedded proteins

In this paper, we look at the expressive power of P systems with proteins embedded on the membranes. The rules governing the evolution of the embedded proteins are inspired from brane calculi. We use some basic operations of brane calculi, namely, exo, endo, bud, mate, pino, wrap in the formalism of membrane computing. We also use rules allowing the movement of proteins, to pass through membranes and attach to and detach from the membranes. Combining the two kinds of operations, namely, brane calculi operations as well as protein movement operations, we have obtained some universality results of P systems. We have also identified some decidable sub-classes of P systems by restricting the use of the protein movement rules.     

P systems with minimal parallelism

A current research topic in membrane computing is to find more realistic P systems from a biological point of view, and one target in this respect is to relax the condition of using the rules in a maximally parallel way. We contribute in this paper to this issue by considering the minimal parallelism of using the rules: if at least a rule from a set of rules associated with a membrane or a region can be used, then at least one rule from that membrane or region must be used, without any other restriction (e.g., more rules can be used, but we do not care how many). Weak as it might look, this minimal parallelism still leads to universality. We first prove this for the case of symport/antiport rules. The result is obtained both for generating and accepting P systems, in the latter case also for systems working deterministically. Then, we consider P systems with active membranes, and again the usual results are obtained: universality and the possibility to solve NP-complete problems in polynomial time (by trading space for time).     

Time-free spiking neural P systems

Different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, a realistic definition of nonsynchronized spiking neural P systems (SN P systems, for short) is considered: during the work of an SN P system, the execution times of spiking rules cannot be known exactly (i.e., they are arbitrary). In order to establish robust systems against the environmental factors, a special class of SN P systems, called time-free SN P systems, is introduced, which always produce the same computation result independent of the execution times of the rules. The universality of time-free SN P systems is investigated. It is proved that these P systems with extended rules (several spikes can be produced by a rule) are equivalent to register machines. However, if the number of spikes present in the system is bounded, then the power of time-free SN P systems falls, and in this case, a characterization of semilinear sets of natural numbers is obtained.     

Efficient simulation of tissue-like P systems by transition cell-like P systems

In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution, communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of basic cell-like P systems to this kind of tissue-like P systems.     

Unexpected universality results for three classes of P systems with symport/antiport

Symport and antiport are biological ways of transporting molecules through membranesin ``collaborating' pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute by communication only), then we consider a recently introduced, way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations – multisets: no ordering– and the data structure of the output – strings: linear ordering). A similar remark holds true for the case of analysing P systems, which work in an automata-like manner: the sequence of certain distinguished objects taken from the environment during acomputation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs. Some open problems are also formulated. This revised version was published online in June 2006 with corrections to the Cover Date.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

Spiking neural P systems: An improved normal form

Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computation (such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems without forgetting rules and delay remains to be found.     

P systems with control nuclei: The concept

We describe an extension of P systems where each membrane has an associated control nucleus responsible with the generation of the rules to be applied in that membrane. The nucleus exports a set of rules which are applied in the membrane region (only for one step, but in the usual maximal-parallel way), then the rules are removed and a new iteration of this process takes place. This way, powerful control mechanisms may be included in P systems themselves, as opposed to using the level of “strategies” previously exploited for simulating P systems. The nuclei may contain general programs for generating rules, ranging from those using information on the full system, to more restricted programs where only local information in the nuclei themselves and the associated membranes is used. The latter approach, mixed with a particular mechanism for the representation of the control programs, the rules, and the export procedure is powerful enough for modeling complex biological applications, e.g., to develop a detailed model for cell growth and division in normal and abnormal (tumoral) evolution of biological systems.     

P systems with active membranes and without polarizations

P systems with active membranes but without using electrical charges (polarizations) are shown to be complete for generating recursively enumerable string languages when working on string objects and using only rules with membrane transitions as well as rules with membrane dissolving and elementary membrane division, but also when using various other kinds of rules, even including a new type of rules allowing for membrane generation. In particular, allowing for changing membrane labels turns out to be a very powerful control feature.     

Array-rewriting P systems

We consider array languages (sets of picturesconsisting of symbols placed in the lattice points of the 2D grid) and thepossibility to handle them with P systems. After proving binary normal formsfor array matrix grammars (which, even in the case when no appearance checking isused, are known to generate the array languages of arbitrary array grammars), weprove that the P systems with context-free rules (with three membranes and no control on the communication or the use of rules) are computationally universal, able togenerate all computable array languages. Some open problems are also formulated.     

Results on catalytic and evolution-communication P systems

In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts and evolution-communication P systems. First, the result from Reference,¹⁴⁾ stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes), as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts. Shankara Narayanan Krishna: She is an Assistant Professor in Dept. Computer Science & Engg, IIT Bombay, India. Her research interests are Natural Computing and Formal Methods. Andrei Paun, Ph.D.: He obtained his bachelor degree in Mathematics and Computer Science from the University of Bucharest, Romania. He obtaind his Ph.D. degree in Computer Science, at University of Western Ontario, Canada, under the supervision of Prof. Dr. Sheng Yu, with the thesis “Unconventional Models of Computation: DNA and Membrane Computing”. After graduation he received a postdoctoral felloship from NSERC, Canada and after six months he accepted an assistant professor position in US at Louisiana Tech University.     

On languages generated by asynchronous spiking neural P systems

In this paper, we investigate the languages generated by asynchronous spiking neural P systems. Characterizations of finite languages and recursively enumerable languages are obtained by asynchronous spiking neural P systems with extended rules. The relationships of the languages generated by asynchronous spiking neural P systems with regular and non-semilinear languages are also investigated.