Membrane Computing

P colonies were introduced in 2004 as an abstract computing device evolved from membrane systems – a biologically motivated computational massive parallel model – composed of independent single membrane agents, reactively acting and evolving in a shared environment.

Different variants of the P colonies were derived from original model since that time. What is shown in this paper is not only a list of these variants, but also finding connections between the results related to the computational power.

The use of models is intrinsic to any scientific activity. In particular, formal/mathematical models provide a relevant tool for scientific investigation. This paper presents a new Membrane Computing based computational paradigm as a framework for modelling processes and real-life phenomena. P systems, devices in Membrane Computing, are not used as a computing paradigm, but rather as a formalism for describing the behaviour of the system to be modelled. They offer an approach to the development of models for biological systems that meets the requirements of a good modelling framework: relevance, understandability, extensibility and computability.

P systems with active membranes are a variant of P systems where the membranes can be created during the computation by division of existing ones. Using this feature, one can create an exponential number of membranes in a polynomial time, and use them in parallel to solve computationally hard problems, such as problems in \(\mathbf{NP }\) or even in \(\mathbf{PSPACE }\). This possibility raises many interesting questions concerning the trade–off between time and space needed to solve various classes of computational problems by means of membrane systems. In this paper we concentrate on P systems with active membranes working in sublinear space, with a survey on recent research results concerning such systems.

The continuous expansion and appreciation of the service oriented architecture is due to the standards of loose-coupling and platform independence. Service-Oriented Architecture is the most commonly and effectively realized through web services, and their temporal collaboration commonly referred to as web service composition. In the present scenario, the most popular variant of composition is service orchestration. Orchestration is achieved through a centralized ‘heavyweight’ engine, the orchestrating agent, that makes the  deployment configuration a massive ‘choke-point’. The issue achieves significance when data and compute intensive scientific applications rely on such a centralized scheme. Lately, a lot of research efforts are put in to deploy a scientific application on the cloud, thereby provisioning resources elastically at runtime. In this paper, we aim at eliminating this central ‘choke’ point by presenting a model inspired from ‘Membrane Computing’ that executes a scientific workflow in a decentralized manner. The benefit of this paradigm comes from the natural process of autonomy, where each cell provision resources and execute process-steps on its own. The approach is devised keeping in mind, the feasibility of deployment on a cloud based infrastructure. To validate the model, a prototype is developed and real scientific workflows are executed in-house (with-in the Intranet). Moreover, the entire prototype is also deployed on a virtualized platform with software defined networking, thereby studying the effects of a low bandwidth environment, and dynamic provisioning of resources.

The concept of a matter object being annihilated when meeting its corresponding anti-matter object is investigated in the context of P systems. Computational completeness can be obtained with using only non-cooperative rules besides these matter/anti-matter annihilation rules if these annihilation rules have priority over the other rules. Without this priority condition, in addition catalytic rules with one single catalyst are needed to get computational completeness. Even deterministic systems are obtained in the accepting case. Allowing anti-matter objects as input and/or output, we even get a computationally complete computing model for computations on integer numbers. Interpreting sequences of symbols taken in from and/or sent out to the environment as strings, we get a model for computations on strings, which can even be interpreted as representations of elements of a group based on a computable finite presentation.

Membrane systems (with symbol objects) are distributed controlled multiset processing systems. Non-cooperative P systems with either promoters or inhibitors (of weight not restricted to one) are known to be computationally complete. Since recently, it is known that the power of the deterministic subclass of such systems is subregular. We present new results on the weight (one and two) of promoters and inhibitors, as well as characterizing the systems with priorities only.

We introduce the new concept of toxic objects, objects that must not stay idle as otherwise the computation is abandoned without yielding a result. P systems of many kinds using toxic objects allow for smaller descriptional complexity, especially for smaller numbers of rules, as trap rules can be avoided. Besides presenting a number of tiny P systems generating or accepting non-semilinear sets of (vectors of) natural numbers with very small numbers of rules, we also improve the results for catalytic and purely catalytic P systems: \(14\) rules for generating a non-semilinear vector set and \(29\) rules for generating a non-semilinear number set are sufficient when allowing only the minimal number of two and three catalysts, respectively; moreover, with using toxic objects, these numbers can be reduced to \(11\) and \(17\). Yet only \(23\) rules – without using toxic objects – are needed if we allow for using more catalysts, i.e., five for catalytic P systems and seven catalysts for purely catalytic P systems.

We consider purely catalytic P systems with two catalysts together with promoters and inhibitors on the rules. We show that computational completeness can be achieved in a deterministic way by using atomic promoters or sets of atomic inhibitors. By using atomic inhibitors computational completeness is achieved only with a non-deterministic construction.

Acceptance and recognizability of finite strings by red–green Turing machines are defined via infinite runs on the input string and the way how to distinguish between red and green states. We extend the notion of red–green Turing machines to register machines with an input tape and then to several variants of P automata. In order to allow for correct simulations of infinite computations of register machines, the models of P automata have to avoid trapping leading to unwanted infinite computations. Therefore, besides the original model of P automata using antiport rules we here consider two models introduced just recently and also allowing for deterministic simulations of register machine instructions, i.e., we consider the models of P systems with anti-matter as well as catalytic P systems with toxic objects. For all these models of P automata we define their red–green variants and show that they can simulate red–green register machines and therefore red–green Turing machines.

Kernel P systems integrate in a coherent and elegant manner many of the features of different P system variants, successfully used for modelling various applications. In this paper, we present our initial attempt to extend the software framework developed to support kernel P systems: a formal verification tool based on the NuSMV model checker and a large scale simulation environment based on FLAME. The use of these two tools for modelling and analysis of biological systems is illustrated with a synthetic biology example.

P colonies were introduced in 2004 (see [10]) as an abstract computing device composed of independent single membrane agents, reactively acting and evolving in a shared environment. Each agent is equipped with a set of rules which are structured into simple programs. There are some models based on from original P colony. In most cases, models are equipped with such components which are associated with the environment. This is the case of Pcol automaton too. The agents work not only with environment but also with an input tape. We use this two theoretical computational devices to build complex robot controllers. In this paper we introduce simple controllers; the first one is used for fulfilling instructions and the other one for passing the maze using right-hand rule. We followed two different approaches and ideas and we present the obtained results in this paper.

Multienvironment P systems constitute a general, formal framework for modelling the dynamics of population biology, which consists of two main approaches: stochastic and probabilistic. The framework has been successfully used to model biologic systems at both micro (e.g. bacteria colony) and macro (e.g. real ecosystems) levels, respectively.

In Membrane Computing, the solution of a decision problem \(X\) belonging to the complexity class P via a polynomially uniform family of recognizer P systems is trivial, since the polynomial encoding of the input can involve the solution of the problem. The design of such solution has one membrane, two objects, two rules and one computation step. Stricto sensu, it is a solution in the framework of Membrane Computing, but it does not use Membrane Computing strategies. In this paper, we present three designs of uniform families of P systems that solve the decision problem STCON by using Membrane Computing strategies (pure Membrane Computing techniques): P systems with membrane creation, P systems with active membranes with dissolution and without polarizations and P systems with active membranes without dissolution and with polarizations. Since STCON is NL-complete, such designs are constructive proofs of the inclusion of NL in \(\mathbf{PMC}_\mathcal{MC}\), \(\mathbf{PMC}_{\mathcal{AM}^0_{+d}}\) and \(\mathbf{PMC}_{\mathcal{AM}^+_{-d}}\).

We prove that every single-tape deterministic Turing machine working in \(t(n)\) time, for some function \(t:\mathbb {N}\rightarrow \mathbb {N}\), can be simulated by a uniform family of polarizationless P systems with active membranes. Moreover, this is done without significant slowdown in the working time. Furthermore, if \(\log t(n)\) is space constructible, then the members of the uniform family can be constructed by a family machine that uses \(O(\log t(n))\) space.

Polymorphic P systems represent a variant of the bio-inspired computational model of P systems, in which the rules are not explicitly given in the description of the system, but are implicitly defined by the contents of certain membranes. In this paper we give a characterisation of the most basic class of such systems, in which only non-cooperative rules are allowed and no ingredients are included. We start by formulating two different formal definitions of non-cooperativity and then show that they have the same generative power. We also show that the generative power of polymorphic P systems is less than \(NRE\) and, finally, that the languages produced by such systems form a hierarchy related to the maximal allowed depth of the membrane structure.

Spiking neural P systems (SN P systems, for short) are a class of distributed parallel computing devices inspired by the way neurons communicate by means of electrical impulses or spikes. SN P systems with astrocytes are a new variant of SN P systems, where astrocytes are introduced to control the amount of spikes passing along synapses. In this work, we investigate the computation power of SN P systems with astrocytes with the rules in any neuron used in the exhaustive manner, that is, the enabled rule in any neuron should be used as many times as possible at any moment. Specifically, it is obtained that such SN P systems can compute/generate any set of Turing computable natural numbers.

The decision problems solved in polynomial time by P systems with elementary active membranes are known to include the class \(\mathbf{P}^{\# \mathbf{P}}\). This consists of all the problems solved by polynomial-time deterministic Turing machines with polynomial-time counting oracles. In this paper we prove the reverse inclusion by simulating P systems with this kind of machines: this proves that the two complexity classes coincide, finally solving an open problem by Păun on the power of elementary division. The equivalence holds for both uniform and semi-uniform families of P systems, with or without membrane dissolution rules. Furthermore, the inclusion in \(\mathbf{P}^{\# \mathbf{P}}\) also holds for the P systems involved in the P conjecture (with elementary division and dissolution but no charges), which improves the previously known upper bound \(\mathbf{PSPACE}\).

The paper considers spiking neural P systems (SN P systems) with cooperating rules where each neuron has the same number of sets of rules, labelled identically. Each set is called a component (maybe empty). At each step only one of the components can be active for the whole system, and only the rules from the active component are enabled. Each neuron with enabled rules from this active component can fire. By using 59 neurons, a small universal SN P system with two components, working in the terminating mode, is constructed for computing functions.

Based on our earlier complex objects proposal, we present three novel concurrent membrane computing models for a fundamental image processing task: the thinning (or skeletonisation) of binary images, based on the classical Guo-Hall algorithm (A2). The first model is synchronous and uses one cell per pixel and relies on inter-cell parallelism; the second model is an asynchronous version of the first; the third model uses one single cell, with one sub-cellular object per pixel, and relies on intra-cell parallelism. The static and dynamic qualities of our models validate our complex objects proposal: (i) the proposed models are crisp (comparable to the best pseudocode); and (ii) complex objects concurrency and messaging can be efficiently emulated on a message-based Actors framework (which opens a novel research path).

An approach to the computational complexity beyond the known complexity measures of the consumed time and space of computation is proposed. The approach focuses on the chaotic behavior and randomness aspects of computational processes and is based on a representation of these processes by causal nets.

This work presents a hybrid model of high performance computations, representing the P system framework with additional quantum functionalities. This model is supposed to take advantages of both biomolecular and quantum paradigms and to overcome some of their inherent limitations. We extend a recently proposed formal model of interface between a membrane system and quantum sub-systems. The problem of finding the longest common subsequence for a set of strings is exhibited as an example.

This paper discusses the application of fuzzy reasoning spiking neural P systems with real numbers (rFRSN P systems) to fault diagnosis of electric locomotive systems. Relationships among breakdown signals and faulty sections in subsystems of electric locomotive systems are described in the form of fuzzy production rules firstly and then fault diagnosis models based on rFRSN P systems for these subsystems are built according to these rules. Fuzzy production rules for diagnosing electric locomotive systems are abstracted from the fault diagnosis analysis of the subsystems and the causality among faulty sections, faulty subsystems and electric locomotive systems. Finally, a diagnosis model based on rFRSN P systems for electric locomotive systems is proposed.