Membrane Computing

Frontmatter

Proton Pumping P Systems

Abstract

We propose here a (biologically inspired) model of P system called proton pumping P system that is a special case of evolution–communication P system. In cell biology there are transport mechanisms, involving protons. We generalize this idea by considering a few different types of protons. A proton pumping P system is, essentially, an evolution–communication P system where a special subset of symbol-objects (called protons) is used. In such a system we have simple evolution rules (classical evolution rules without target indications), symport and antiport rules that exchange some objects (among them, possibly, other protons) for a proton; taking inspiration from biology, this particular type of antiports is often called proton pumping rules.

We show that, as expected, the new model is universal, using non-cooperative rules, symport and antiport rules of weight one, and enough types of protons available for the computation. If we decrease the number of types of protons to one or two, then the model is at least as powerful as ET0L system, provided that (total) weak or strong priority of antiport rules over symport and evolution rules are used.

Finally, we consider some descriptional complexity measures (again, inspired from biology) for the newly introduced model.

Artiom Alhazov, Matteo Cavaliere

A Binary Data Structure for Membrane Processors: Connectivity Arrays

Abstract

This paper defines membrane processors as digital processors capable of implementing local processing performed inside membranes in transition P systems. In order to encode the membrane structures of transition P systems, additional binary data structures are needed. Such binary data structures are named ”connectivity arrays”. The main purposes of the connectivity arrays are to distribute information about the system membrane structure among the different processors that implement the transition P system, and to facilitate communication processes among different membrane processors. The information kept in processor has to be versatile and compact; versatile means to easily permit changes in the membrane structure of the system processors, and compact means that not too much memory space is needed.

Considering these two requests, a binary word of variable length is considered here in order to represent in membrane processors the local information about the membrane structures of transition P systems. This paper presents the abstract data type “connectivity array” which defines the data structure and the needed operations over it in order to parse the P system into a membrane processor tree and to keep congruent the P system membrane structure with the membrane processor tree.

Fernando Arroyo, Juan Castellanos, Carmen Luengo, Luis F. Mingo

Parsing with Active P Automata

Abstract

New classes of P automata are introduced corresponding to the basic classes of languages in the Chomsky hierarchy. Unlike the previously defined P automata, active P automata are computing with the structure of the membrane systems, using operations like membrane creation, division and dissolution. The model is applied to the parsing of (natural language) sentences into dependency trees.

Gemma Bel-Enguix, Radu Gramatovici

Universality of Minimal Symport/Antiport: Five Membranes Suffice

Abstract

P systems with symport/antiport rules of a minimal size (only one object passes in any direction in a communication step) have been recently proved to be computationally universal. The result originally reported in [2] has been subsequently improved in [6] by showing that six membranes suffice. In [6] it has been also conjectured that at least one membrane can be saved. Here we prove that conjecture: P systems with five membranes and symport/antiport rules of a minimal size are computationally complete. The optimality of this result remains open.

Francesco Bernardini, Andrei Păun

Collapsing Hierarchies of Parallel Rewriting P Systems without Target Conflicts

Abstract

We continue the investigation of parallel rewriting P systems without target conflicts, a class of rewriting P systems with parallel application of evolution rules where the possible consistency problems for the communication of the resulting strings are eliminated by not allowing the application of conflicting rules. We refine and improve some of the previously known results about the generative power of these systems and point out the problems which are still open for investigation.

Daniela Besozzi, Giancarlo Mauri, György Vaszil, Claudio Zandron

Evolution and Observation: A New Way to Look at Membrane Systems

Abstract

An architecture for investigating the dynamical behaviour of biological systems is proposed by using the concepts of “behaviour” and “observer”. The behaviour of a biological system is the sequence of states traversed as time passes; the observer is a device translating this behaviour into a readable output.

As an instance of this architecture we investigate P/O systems constituted by a membrane system and a multiset finite automaton observer. We first characterize the infinite behaviours of conservative systems, i.e., systems whose number of objects is constant. These systems behave very regularly. For more sophisticated systems we then use also more complicated multiset automata as observers: they map the configurations into an output alphabet and thus we obtain words describing the entire computations. Even for seemingly simple membrane systems using only non-cooperative rules and regular-like observers through this combination a great power emerges, in our case computational universality.

Matteo Cavaliere, Peter Leupold

Tiling Rectangular Pictures with P Systems

Abstract

We introduce a class of two-dimensional tiling languages which are distinct from the local and recognizable picture languages. These languages arise from tilings of the integer lattice Z ². For such picture languages, we define a class of tissue-like P systems with active membranes as a generative device. We also make a comparison with the model introduced in [2,3] for the generation of local and recognizable two-dimensional languages, using a similar type of P systems.

Rodica Ceterchi, Radu Gramatovici, Nataša Jonoska

Simulating Boolean Circuits with P Systems

Abstract

We propose a model for simulating Boolean circuits with P systems. The simulation is done in two steps, by first simulating the gates of such a circuit, and next by showing how these can be combined to obtain actual circuits. The type of P systems used is with symbol objects, context-free rewriting rules and some other features like mobile catalysts, weak priorities and promoters.

Rodica Ceterchi, Dragoş Sburlan

P Systems Running on a Cluster of Computers

Abstract

The paper presents a parallel implementation of the membrane systems. We implement the simplest variant of P systems, which however defines the essential features of the membrane systems, and acts as a framework for other variants of P systems with advanced functionalities. The mechanisms used in this implementation could be easily adapted to other versions of P systems with minor changes. The implementation is designed for a cluster of computers; it is written in C++ and it makes use of Message Passing Interface as its communication mechanism.

Gabriel Ciobanu, Guo Wenyuan

Implementing in Prolog an Effective Cellular Solution to the Knapsack Problem

Abstract

In this paper we present an implementation in Prolog of an effective solution to the Knapsack problem via a family of deterministic P systems with active membranes using 2-division.

Andrés Cordón-Franco, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez, Agustin Riscos-Núñez, Fernando Sancho-Caparrini

On the Dynamics of PB Systems: A Petri Net View

Abstract

We study dynamical properties of PB systems, a new computational model of biological processes, and propose a compositional encoding of PB systems into Petri nets. Building on this relation, we show that three properties: boundedness, reachability and cyclicity, which we claim are useful in practice, are all decidable.

Silvano Dal Zilio, Enrico Formenti

P Systems Generating Hexagonal Picture Languages

Abstract

P systems generating rectangular arrays have been recently introduced in [1,2,3], thus bringing together the two areas of theoretical computer science, namely membrane computing and picture grammars. In this paper, hexagonal arrays on triangular grids are considered and the capabilities of the three approaches [1,2,3] that construct P systems for generation of arrays on rectangular grids, to handle arrays on triangular grids, are demonstrated.

K. S. Dersanambika, Kamala Krithivasan, K. G. Subramanian

A Membrane System for the Leukocyte Selective Recruitment

Abstract

A formal description is developed for the phenomenon of leukocyte recruitment that plays a critical role in the immune response. Due to its complex nature and capability to rapidly adapt to the attack of infectious agents, the immune system may be considered a typical example of complex adaptive system [9].

Here the leukocyte selective recruitment, crucial in immunity, is modeled as a dynamical system of interactions between leukocytes and endothelial cells, where a special kind of membrane structure turns out to be a very useful tool in the formal analysis of the recruitment process. In our membrane system, besides the traditional rules for communication and transformation of P systems [8], rules are allowed for the expression of receptors, for adhesion between membranes, and for the encapsulation of a membrane inside another membrane.

Giuditta Franco, Vincenzo Manca

P Systems with Cutting/Recombination Rules Assigned to Membranes

Abstract

We introduce a new variant of splicing P systems, where the rules are directly assigned to the membranes and not to the regions as this is usually observed in the area of membrane systems. The strings involved in the splicing operation are either taken from inside or from outside the membrane and the strings resulting from the splicing operation also may go inside or outside the membrane. Instead of the splicing operation, also the operations of cutting and recombination are used as rules assigned to membranes. For the application of rules leading from one configuration of the system to the succeeding configuration we consider a sequential model and do not use the model of maximal parallelism. We will show that for such sequential P systems using splicing rules or cutting/recombination rules assigned to the skin membrane we already obtain universal computational power with only one membrane.

Franziska Freund, Rudolf Freund, Marion Oswald, Maurice Margenstern, Yurii Rogozhin, Sergey Verlan

ω -P Automata with Communication Rules

Abstract

We introduce ω -P automata based on the model of P systems with membrane channels (see [8]) using only communication rules. We show that ω -P automata with only two membranes can simulate the computational power of usual (non-deterministic) ω -Turing machines. A very restricted variant of ω -P automata allows for the simulation of ω -finite automata in only one membrane.

Rudolf Freund, Marion Oswald, Ludwig Staiger

The Number of Membranes Matters

Abstract

We look at a restricted model of a communicating P system, called RCPS, whose environment does not contain any object initially. The system can expel objects into the environment but only expelled objects can be retrieved from the environment. Such a system is initially given an input \(a_1^{i_1} ... a_n^{i_n}\) (with each i _j representing the multiplicity of distinguished object a _i , 1 ≤ i ≤ n) and is used as an acceptor. We show that RCPS’s are equivalent to two-way multihead finite automata over bounded languages (i.e., subsets of \(a_1^* ... a_n^*\), for some distinct symbols a ₁, ..., a _n ). We then show that there is an infinite hierarchy of RCPS’s in terms of the number of membranes. In fact, for every r, there is an s> r and a unary language L accepted by an RCPS with s membranes that cannot be accepted by an RCPS with r membranes. This provides an answer to an open problem in [12] which asks whether there is a nonuniversal model of a membrane computing system which induces an infinite hierarchy on the number of membranes. We also consider variants/generalizations of RCPS’s, e.g., acceptors of languages; models that allow a “polynomial bounded” supply of objects in the environment initially; models with tentacles, etc. We show that they also form an infinite hierarchy with respect to the number of membranes (or tentacles). The proof techniques can be used to obtain similar results for other restricted models of P systems, like symport/antiport systems.

Oscar H. Ibarra

An Agent-Based Behavioural Model of Monomorium Pharaonis Colonies

Abstract

In this study X-machines and hierarchical organized X-machines will be used to model different aspects of the behaviour of social insect communities. The model is organized as a community of complex agents showing similarities to networks of P systems.

Duncan Jackson, Marian Gheorghe, Mike Holcombe, Francesco Bernardini

Can Hyperbolic Geometry Be of Help for P Systems?

Abstract

The goal of this paper is to propose a possible new approach to P systems by making use of hyperbolic geometry. The ideas of the paper are a continuation of the ideas which the author presented at the ”Brainstorming meeting” organised in Tarragona, Spain, on February 5-12, 2003. The hope of this approach is that this could be of some help in order to better understand the computational power of Nature.

Maurice Margenstern

A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes

Abstract

Up to now, P systems dealing with numerical problems have been rarely considered in the literature. In this paper we present an effective solution to the Knapsack problem using a family of deterministic P systems with active membranes using 2-division. We show that the number of steps of any computation is of linear order, but polynomial time is required for pre-computing resources.

Mario J. Pérez-Jiménez, Agustin Riscos-Núñez

A Reconfigurable Hardware Membrane System

Abstract

P systems are massively parallel systems and software simulations do no usually allow to exploit this parallelism. We present a parallel hardware implementation of a special class of membrane systems. The implementation is based on a universal membrane hardware component that allows to efficiently run membrane systems on specialized hardware such as FPGAs. The implementation is presented in detail as well as performance results and an example.

Biljana Petreska, Christof Teuscher

P Systems and Petri Nets

Abstract

We propose an intriguing relationship between P systems and Petri nets. For a basic model of P systems, this paper presents a new formalization based on place/transition nets, which can adopt one transition to implement the structural operational semantics of one evolving rule in P systems and utilize incidence matrix to analyze the computation of one macro-step. We also define the behavioral properties in P systems such as terminating, liveness, and boundedness based on this formalization. For a general class of P systems, we briefly describe a high-level framework called membrane Petri nets (MP-nets). MP-nets extend ordinary colored Petri nets (CPN) through introducing the dynamic features such as dissolve, divide, and move inspired by P systems. Therefore, MP-nets can be a graphical as well as an algebraic modelling tool for both generic P systems and dynamic CPN.

Zhengwei Qi, Jinyuan You, Hongyan Mao

Simulation of Mobile Ambients by P Systems. Part 1

Abstract

Ambient calculus is an abstract model of the basic features of distribution and mobility of the computing and computation. The central notion of ambient calculus is that of a mobile ambient, which is a bounded place where a computation happens. It was shown that a P system with symbol-objects with membrane dissolution can be expressed in ambient calculus. We want to do here the converse work: to express ambient calculus in membrane computing. In this paper we present the first part of this work: we show that the Ethernet Network (local electronic computer network) can be expressed in terms of P systems with symbol-objects.

Vladimir Rogozhin, Elena Boian

Computing Partial Recursive Functions by Transition P Systems

Abstract

In this paper a variant of transition P systems with external output designed to compute partial functions on natural numbers is presented. These P systems are stable under composition, iteration and unbounded minimization (μ–recursion) of functions. We prove that every partial recursive function can be computed by such P systems, from which the computational completeness of this model can be deduced.

Alvaro Romero-Jiménez, Mario J. Pérez-Jiménez

P Systems with External Input and Learning Strategies

Abstract

This is a preliminary work in which we propose a variant of P systems by adding in every region a dynamic engine that allows the change of the internal rewriting rules along the computation time, obtaining in this way a new family of P systems with adaptation to changing environments. They will be called adaptative P systems. Here, the engine that we propose to act inside every membrane is based on learning algorithms under the grammatical inference framework. The behavior of every region changes according to the information received from the external environment and the internal regions.

José M. Sempere

A Distributed Simulation of Transition P Systems

Abstract

P systems is a new model of computation, inspired by natural processes, that has a distributive nature. By exploring this distributive nature of P systems, we have built a purely distributive simulation of P systems. The simulation, whose implementation is described here, was programmed in the Java programming language and makes heavy use of its Remote Method Invocation protocol. The class of P systems that the simulator can accept is a subset of the NOP₂(coo, tar) family of systems, which have the computational power of Turing machines. The paper concludes with some remarks concerning the usefulness of the simulation. In addition, there is a brief discussion of some ideas that can be used in the formulation of a foundation of distributive computing.

Apostolos Syropoulos, Eleftherios G. Mamatas, Peter C. Allilomes, Konstantinos T. Sotiriades

About Splicing P Systems with Immediate Communication and Non-extended Splicing P Systems

Abstract

We consider splicing P systems with immediate communication introduced by Gh. Păun in [5]. We solve the open problem Q17 from that book by proving that systems with two membranes can generate any recursively enumerable language. We discuss the similarities between splicing P systems with immediate communication having two membranes and time-varying distributed H systems with two components. We also consider non-extended splicing P systems, i.e., without a terminal alphabet. We show that it is possible to generate any recursively enumerable language by such systems with two membranes. In this way we solve the open problem Q16 from the same book.

Sergey Verlan

Backmatter