Chapter 1
A Gentle Introduction to Membrane Systems and Their Computational Properties
Alberto Leporatiā, Luca Manzoniā , Giancarlo Mauriā”,
Antonio E. PorrecaĀ§ and Claudio ZandronĀ¶
Membrane computing, known as a novel branch in computer science, has gain plenty of results in both theoretical and application levels. In this chapter, a gentle introduction to membrane systems and their computational properties is discussed. Membrane structures, the content of region, computation rules are recalled, as well as the formal definition of membrane systems is given. The computational power, as both generating and accepting deceives are shown, and the computational efficiency are discussed by solving computational hard problems by membrane systems.
1.1.Introduction
The theory of computation investigates the nature and properties of algorithmic procedures. This field emerged in the 1920s and 1930s of the 20th century from the work on the philosophy and the foundations of mathematics. Of great importance and inspiration was David Hilbertās ambitious program to ādispose of the foundational questions in mathematics once and for allā [34], that led to fundamental results in logic such as Gƶdelās incompleteness theorems [6], and ultimately to the birth of recursion theory (nowadays mostly referred to as computability theory) and computer science itself.
The formal notion of computability that is almost universally adopted today is due to Alan Turing, who introduced in his ground-breaking paper [32] a simple, elegant and convincing mathematical formalization of the notion of computation, as it is carried out by a human executor equipped with enough scratch paper. Turingās work showed that, as long as we accept his notion of computation, there exist well-formed mathematical questions whose answer cannot be computed. In particular, one of the main challenges of Hilbertās program, the Entscheidungsproblem (finding a decision procedure for the validity of statements in first-order logic) was proved to be unsolvable.
This formalization, that rapidly became known as the Turing machine, is still the reference model for computing devices in theoretical computer science, as it also enjoys the property of being a good model of actual electronic computers; this is also due to the fact that it was itself an inspiration for the design of automatic computing machinery [5].
With the development of computers as a technology, being able to solve a particular problem proved not to be satisfying: fast, efficient solutions are needed. This led to the development of computational complexity theory, pioneered [9] by Hartmanis and Stearns in [12], which also gives the name to the field. Identifying the notion of āefficientā with āpolynomial-time computableā is due [9] to Edmonds [7], while the central question of complexity theory, whether P = NP, arose from the work of Cook [4] and Karp [16]. This question has shaped the whole development of the field and still remains open today.
However, the theory of computation is not entirely about Turing machines. Several authors sought to draw inspiration from the way nature ācomputesā in order to define alternative, unconventional computing models or, from the opposite point of view, to interpret natural phenomena as computation [1]. For instance, artificial neural networks [21] are inspired by the functioning of neurons in the brain, and genetic algorithms seek to solve computationally hard problems by simulating the processes of mutation, mating and natural selection. A clear example of biological inspiration is given by DNA computing, which provided an actual in vitro implementation of an algorithm for the Hamilton path problem [2] (the theory was initiated a few years earlier, particularly by Head [13]).
Inspired by the work on DNA computing [26], Pun introduced in 1998 (see [24]) the notion of membrane systems, initially called super-cells, and nowadays usually known as P systems. Here the computing device is an abstraction of biological cells. Unlike in neural networks, we do not deal with cells as atomic objects: as the name suggests, the focus is on the membranes that define the cells and their internal compartments, which work together by performing different individual functions. The chemical environment of the various compartments are described in terms of multisets of symbols (i.e. sets in which each symbol has a multiplicity). Another defining feature of P systems (as they were initially defined) is maximal parallelism: as many operations as possible are carried out simultaneously, and no part of the system remains inactive if it can carry out some part of the computation.
Although P systems have also been investigated from the perspectives of bioinformatics and systems biology, where they might be used as models of biological phenomena in computer simulations, most of the research in membrane computing has been carried out from a language-theoretic (including the seminal paper [24]), computability-theoretic and complexity-theoretic standpoint.
In the literature, many variants using various kinds of rules and different features have been considered and investigated in this respect. For example, the notion of multiset rewriting employed in the original model of the P system [24] is context-sensitive (or cooperative, which is the term normally used in membrane computing). Other classes of P systems, however, possess other features that make them extremely powerful from a computational perspective: as a consequence, the use of context-free (or non-cooperative) rewriting rules has also been considered. Here, for the sake of explanation, we will present a simplified model using only the basic ingredients and simple cooperative rewriting rules. After presenting some basic definitions, we will first show that such systems are Turing complete, by simulating register machines, a well-known universal computing device, and we will show that the direct simulation of Turing machines is time efficient. Then, by exploiting the possibility of creating new membranes by division of existing ones, we will show how to solve all the problems from the complexity classes NP and PSPACE in polynomial time (and exponential space) by means of membrane systems. At the end of the chapter, we will shortly discuss how cooperation can be avoided, and we will provide pointers to the literature concerning main variants considered in the framework of membrane computing.
1.2.Membrane Structures
The main feature of all variants of P systems is their membrane structure. Several variants have been proposed in the literature [27], but we consider here the original cell-like shape [24]: a hierarchy of membranes nested to an arbitrary depth. There is a clear bijective mapping between the set of membranes and the regions they define, delimited by the membrane itself from the outside, and any membrane immediately included in it from the inside. The outermost membrane (sometimes called the skin) separates the actual P system from the surrounding environment, which is a furth...