Membrane Computing

We aim to compare functionality of symport/antiport with embedded rewriting to that of symport/antiport accompanied by rewriting, by two-way simulation, in case of tissue P systems with parallel communication. A simulation in both directions with constant slowdown is constructed.

P systems are a model of hierarchically compartmentalized multiset rewriting. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We define three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides.

We study the controlled reversibility in reaction systems, a bio-inspired formalism in which the reactions take place only if some inhibitors are not present. Forward reactions are exactly those of the reaction systems, while reverse reactions happen when a special symbol indicates a change in the environment. The reversible reaction systems are translated into rewriting systems which are executable on the Maude software platform. Given such an implementation, several properties of the reversible reaction systems could be verified.

In this paper we investigate dynamic causalities in membrane systems by proposing the concept of “predictor”, originally defined in the context of Ehrenfeucht and Rozemberg’s reaction systems. The goal is to characterize sufficient conditions for the presence of a molecule of interest in the configuration of a P system after a given number of evolution steps (independently from the non-deterministic choices taken). Such conditions can be used to study causal relationships between molecules. To achieve our goal, we introduce the new concept of “multiset pattern” representing a logical formula on multisets. A predictor can be expressed as a pattern characterizing the initial multisets that will surely lead (sufficient condition) to the presence of the molecule of interest after the given number of evolution steps. We define also an operator that computes such a predictor.

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 are very attractive from a computational complexity point of view: if X is an NP-complete problem then the counting version \(\# X\) is NP-hard, but the counting version of some problems in class P can also be NP-hard. In this paper, a new class of membrane systems is presented in order to provide a natural framework to solve counting problems. The class is inspired in a special kind of non-deterministic Turing machines, called counting Turing machines, introduced by L. Valiant. A polynomial-time and uniform solution to the counting version of the SAT problem (a well-known \(\#\) P-complete problem) is also provided, by using a family of counting polarizationless P systems with active membranes, without dissolution rules and division rules for non-elementary membranes but where only very restrictive cooperation (minimal cooperation and minimal production) in object evolution rules is allowed.

We investigate the possibility of “going beyond” Turing in the terms of Automaton-like P Colonies (APCol systems, for short), variants of P colonies processing strings as their environments. We use the notion of teams of agents as a restriction for the maximal parallelism of the computation. In addition, we assign a colour to each team. In the course of the computation, the colour is changing according to the team that is currently active. We show that we can simulate red-green counter machines with APCol systems with two-coloured teams of minimal size. Red-green counter machines are computing devices with infinite run on finite input that exceed the power of Turing machines.

The general concept, called the formal framework of P systems provides a representation to study and analyze different variants of P systems. In this paper, two well-known models, P colonies and P systems with multi-stable catalysts are considered. We show that the obtained representations are identical, thus both models can be related using a bi-simulation. This fact opens new approaches for studying both P colonies and catalytic P systems.

Generalized communicating P systems are particular variants of networks of cells where each rule moves only two objects. In this paper we show that GCPSs with three cells and with only join, or only split, or only chain rules are computationally complete computing devices. These bounds are improvements of the previous results.

A sequence of perceivable events or recorded observations over time commonly witnesses the life cycle of an individual at a macroscopic perspective. In case of a human being, birth could make the starting point followed by successive maturation along with increase of individual skills. Further events like foundation of a family, stages of career, coping with dramatic diseases, loss of abilities, and finally the death mark crucial events within a human life cycle. Even beyond biology, life cycles are present in various contexts, for instance when elucidating the quality of durable technical products such as cars. Social scenarios or games with several players incorporate consideration of life cycles as well. Provided by logfiles or monitoring reports, dedicated accumulation of events facilitates identification of life cycles whose statistical analysis promises valuable insights. To this end, we formalise an individual by a set of attributes. Based on its underlying initial assignment (“genetic potential”), events can update corresponding attribute values. Furthermore, events might create new individuals but also kill or merge existing ones. For modelling and evaluation of life cycles, we introduce action-accumulating P systems inspired by dealing with events which in turn result in actions at the system’s level. Two case studies demonstrate practical benefits from our approach: We explore the survival of pieces in the board game Mensch ärgere Dich nicht (Man, don’t get annoyed – a variation of Ludo). Secondly, we interpret pseudonymised data from 1,108 students who attended our university course Introduction to Programming stating main factors to improve the final grade with emphasis on the effect of passing a line of exercises and practical training offers.

We explore the computing power of Evolution-Communication P systems with energy (ECPe systems) considering dynamical communication measures, ComN, ComR and ComW. These measures consider the number of communication steps, communication rules and total energy used per communication step, respectively. In this paper, we address a previous conjecture that states that only semilinear sets can be generated with bounded ComX, \(X \in \{N,R,W\}\). Our result on bounded ComW seems to support such conjecture while the conjecture is not true for bounded ComN and ComR. We also show that the class of recursively enumerable sets can be computed using ECPe systems with two membranes. This improves a previous result that makes use of four membranes to show computational completeness.

This paper illustrates how kernel P systems (kP systems) can be used for modelling and validating an engineering application, in this case a cruise control system of an electric bike. The validity of the system is demonstrated via formal verification, carried out using the kPWorkbench tool. Furthermore, we show how the kernel P system model can be tested using automata and X-machine based techniques.

We solve affirmatively a new special case of the P conjecture by Gh. Păun, which states that P systems with active membranes without charges and without non-elementary membrane division cannot solve \(\mathbf {NP}\)-complete problems in polynomial time. The variant we consider is monodirectional, i.e., without send-in communication rules, shallow, i.e., with membrane structures consisting of only one level besides the external membrane, and deterministic, rather than more generally confluent. We describe a polynomial-time Turing machine simulation of this variant of P systems, exploiting a generalised version of dependency graphs for P systems which, unlike the original version introduced by Cordón-Franco et al., also takes membrane dissolution into account.

Finding the most common words in a text file is a famous “programming pearl”, originally posed by Jon Bentley (1984). Several interesting solutions have been proposed by Knuth (an exquisite model of literate programming, 1986), McIlroy (an engineering example of combining a timeless set of tools, 1986), Hanson (an alternate efficient solution, 1987). Here we propose a concise efficient solution based on the fast parallel and associative capabilities of cP systems. We also check their parallel sorting capabilities and propose a dynamic version of the classical pigeonhole algorithm.

Tissue P systems are computational models inspired by the way of biochemical substance movement/exchange between two cells or between a cell and the environment, where all communication (symport/antiport) rules used in a system are initially set up and keep unchanged during any computation. In this work, a variant of tissue P systems, called tissue P systems with rule production/removal (abbreviated as TRPR P systems) is considered, where rules in a system are dynamically changed during a computation, that is, at any computation step new rules can be produced and some existing rules can be removed. The computation power of TRPR P systems is investigated. It is proved that Turing universality is achieved for TRPR P systems with one cell, and using symport rules of length at most 1, antiport rules of length at most 2 or symport rules of length at most 2 and working in a maximally parallel manner. We further show that TRPR P systems with two cells, using symport rules of length at most 1, and working in a flat maximally parallel manner, are Turing universal.

The issue of reversibility in computational paradigms has gained interest in recent years. In this paper we investigate how to reverse steps in membrane systems computations. The problem is that computation steps in membrane systems do not preserve all the information that has to be used when reversing them. We try to formalize the relevant information needed, and we show that the proposed approach enjoy the so called loop lemma, which basically assures that the undoing obtained by reversely applying rules is correct.

In this work, we propose the study of SN P systems as classical information encoders. By taking the spike train of an SN P system as a (binary) source of information, we can obtain different languages according to a previously defined encoding alphabet. We provide a characterization of the language families generated by the SN P systems in this way. This characterization depends on the way we define the encoding scheme: bounded or not bounded and, in the first case, with one-to-one or non injective encodings. Finally, we propose a network topology in order to define a cascading encoder.

The time appears ripe to enrich the original idea of membrane computing with principles of self-assembly in space. To this effect, a first step was taken with the introduction of a new such family of models M systems (for morphogenetic system) that own a number of basic macro-properties exhibited by higher living organisms (such as self-assembly, cell division akin to mitosis and self-healing), while still only leveraging local interactions of simple atomic components and explicit geometric constraints of their constituting elements. Here we further demonstrate that, experimentally in silico, M systems are in general also capable of demonstrating these properties robustly after being assembled from scratch from some atomic components and entering a homeostatic regime. The results are obtained through a series of experiments carried out with an M system simulator designed to implement this kind of model by researchers interested in exploring new capabilities. We further define probabilistic complexity classes for M systems and we show that the model is theoretically capable of solving NP-complete problems in P-time, despite apparent problems of an implementation, such as kinetic and concentration bottlenecks.