Narrow Results

Membrane Computing is a recently introduced area of Molecular Computing, where a computation takes place in a membrane structure where multisets of objects evolve according to given rules (they can also pass through membranes). The obtained computing models were called P systems. In basic variants of P systems, the use of objects evolution rules is regulated by a given priority relation; moreover, each membrane has a label and one can send objects to precise membranes, identified by their labels. We propose here a variant where we get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an "electrical charge" and the objects are passed through membranes according to their charge. We prove that such systems are able to characterize the one-letter recursively enumerable languages (equivalently, the recursively enumerable sets of natural numbers), providing that an extra feature is considered: the membranes can be made thicker or thinner (also dissolved) and the communication through a membrane is possible only when its thickness is equal to 1. Several open problems are formulated.

In this paper we define a variant of P systems, namely, probabilistic rewriting P systems, where the selection of rewriting rules is probabilistic. We show that, with non-zero cut-point, probabilistic rewriting P systems with/without priorities generate only finite languages, but with zero cut/point and without priorities, probabilistic rewriting P systems of degree 1 characterize the family of languages generated by matrix grammars. We also prove that probabilistic rewriting P systems of degree 1 with zero cut-point and priorities characterize recursively enumerable languages.

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.

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.

This paper presents several results regarding P systems with non-cooperative rules and promoters/inhibitors at the level of rules. For the class of P systems using inhibitors, generating families of sets of vectors of numbers, a characterization of the family of Parikh sets of ET0L languages is shown. In the case of P systems with non-cooperative promoted rules even if an upper bound was not given, the inclusion of the family PsET0L was proved. Moreover, a characterization of such systems by means of a particular form of random context grammars, therefore a sequential formal device, is proposed.

We consider the problem of synchronizing the activity of all the membranes of a P system. After pointing at the connection with a similar problem dealt with in the field of cellular automata where the problem is called the firing squad synchronization problem, FSSP for short, we provide two algorithms to solve this problem. One algorithm is non-deterministic and it works in the time 3h, where h is the height of the tree defining the membrane structure of the considered P system. The other algorithm is deterministic and it works in time 4n + 2h, where n is the number of membranes of the considered P system. Finally, we suggest various directions to continue this work.

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.

In this paper we propose an extension of a systems/synthetic biology modelling framework based on P systems that explicitly includes modularity. Modularisation in cellular systems can be produced by chemical specificity, spatial localisation and/or temporal modulation within cellular compartments. The first two of these modularisation features, the focus of this paper, can be easily specified and analysed in P systems using sets of rewriting rules to describe chemical specificity and membranes to represent spatial localisation. Our methodology enables the assembly of cell systems biology models by combining modules which represent functional subsystems. A case study consisting of a bacterial colony system is presented to illustrate our approach.

The paper is a survey of the recent model of P systems with proteins on membranes introduced by Păun and Popa in 2006. This model can be viewed as an extension of the highly successful paper of (Păun and Păun 2002) describing P systems based on symport/antiport. The previous model represented an important change of direction from strings to objects in the area of P systems. The main drawback of the model from 2002 was the massive parallelism that is not seen in real life. The 2006 model was a step in controlling the parallelism the same way it is done in nature in symporters and antiporters: these processes take place through protein channels embedded at the level of the membrane which can only be used by a molecule at a time, thus yielding a sequentiality with respect to the number of such proteins embedded in the membrane.

Multienvironment probabilistic P systems provide a framework of specification for modeling population biology. It has been used to model real ecosystems in a comprehensible, modular and probabilistic way. However, simulators are needed for virtual experimentation. Hence, the development of correct simulation algorithms becomes a critical point. In this paper we present a formal verification of a new algorithm of simulation designed for this kind of probabilistic P systems.

The aim of this paper is to give motivations for the development of operational semantics in membrane computing, and to survey existing proposals. In particular, the definitions are compared of three operational semantics available in the literature, namely a semantics proposed by Andrei, Ciobanu and Lucanu, another proposed by Busi, and another one proposed by the authors of the present paper. These definitions are different since they are given with different aims. However, we show that there is an operational correspondence among the three.

This paper presents an approach to P system verification using the Spin model checker. It proposes a P system implementation in PROMELA, the modeling language accepted by SPIN. It also provides the theoretical background for transforming the temporal logic properties expressed for the P system into properties of the executable implementation. Furthermore, a comparison between P systems verification using SPIN and NUSMV is realized. The results obtained show that the PROMELA implementation is more adequate, especially for verifying more complex models, such as P systems that model ecosystems.

Lately, some studies linked the computational power of abstract computing systems based on multiset rewriting to Petri nets and the computation power of these nets to their topology. In turn, the computational power of these abstract computing devices can be understood just looking at their topology, that is, information flow.

This line of research is very promising for several aspects: (i) its results are valid for a broad range of systems based on multiset rewriting; (ii) it allows to know the computational power of abstract computing devices without tedious proofs; (iii) it links computational power to topology and, in this way, it opens a broad range of questions.

In this paper we summarise the known results on this topic and we list a few suggestions for research together with the relevance of possible outcomes.

In this paper we consider universal systems based on splicing. As in previous works, we take the number of rules as the parameter for the descriptional complexity. We present three results: universal double splicing extended H system with 5 rules, universal splicing test tube system with 8 rules and a universal splicing P system with 5 rules.

P automata are variants of symport/antiport membrane systems which describe string languages by applying a mapping to the sequence of multisets entering the system during computations. In this paper, we study their computational power in the case when the input mapping associates each input multiset with the set of strings consisting of all permutations of its elements. We show that P automata of this type are strictly less powerful than so-called restricted logarithmic space Turing machines, and we also exhibit a strict infinite hierarchy within the accepted language class based on the number of membranes present in the system.

We investigate the spiking neural P systems with communication on request (SNQ P systems) that are devices in the area of neural like P systems abstracting the way in which neurons work and process information. Here we discuss the SNQ P systems using the rule application strategy as defined by Linqiang Pan and collaborators and we are able to improve their result of universality of such systems using two types of spikes. In the current work, we prove that only one type of spikes is sufficient for reaching the computational power of Turing Machines for these devices, bringing closer to implementation such a device. The result holds both in maximum parallel manner application of the rules as well as the maximum-sequentiality application of rules.

We consider tissue P systems working on vesicles of multisets with the very simple operations of insertion, deletion, and substitution of single objects. With the whole multiset being enclosed in a vesicle, sending it to a target cell can be indicated in those simple rules working on the multiset. As derivation modes we consider the sequential derivation mode, where, if possible, one rule is applied in a derivation step, and the set maximally parallel derivation mode, where in each derivation step a non-extendable set of rules indicating the same target cell is applied. With the set maximally parallel derivation mode, computational completeness can already be obtained with tissue P systems having a tree structure, whereas tissue P systems even with an arbitrary communication structure are not computationally complete when working in the sequential mode. Adding polarizations — only the three polarizations $-1$, $0$, $1$ are sufficient — allows for obtaining computational completeness even for tissue P systems working in the sequential mode.

Membrane computing, also known as P system, is a distributed and parallel computation framework models. Hierarchical clustering is one of the most basic and widely applied clustering algorithms among all clustering algorithms. In this paper, the combination of membrane computing and hierarchical clustering algorithm is studied. A cell-like hierarchical clustering P system with priority evolution rules and promoters is designed by using the maximum parallelism of membrane computing. The feasibility and effectiveness of the designed P system are verified by the examples.