Second Brainstorming Week on Membrane Computing
J.UCS Special Issue

Gheorghe Paun (Institute of Mathematics of the Romanian Academy, Bucharest, Romania, and Department of Computer Science and Artificial Intelligence Sevilla University, Spain)
gpaun@us.es

Mario J. Pérez­Jiménez (Department of Computer Science and Artificial Intelligence Sevilla University, Spain)
Mario.Perez@cs.us.es

Abstract: The present volume contains a selection of papers elaborated during the "Second Brainstorming Week on Membrane Computing", held in Sevilla, Spain, from February 2 to February 7, 2004, in the organization of the Research Group on Natural Computing (RGNC) from the Department of Computer Science and Artificial Intelligence of Sevilla University. The goal of this novel type of meetings (the first edition was held in February 2003 in Tarragona, Spain), is to gather together a number of active researchers in membrane computing, for exchanging ideas, presenting recent results, and working together for one week in an informal and friendly environment.

The efficiency of such meetings, prepared in advance by a previous interaction through internet, is very high, and this year the success was still higher than the previous year. In total, 38 researchers were present in Sevilla, com­ puter scientists, mathematicians, biologists, of various ages and from various countries, and an impressive number of research topics, problems, preliminary results were discussed and then turned out into papers. The initial versions of these papers were collected in a proceedings volume which was published soon after the meeting as a technical report (no 1/2004) of RGNC, Sevilla University; the volume, of about 460 pages, is available also through the web page from http://psystems.disco.unimib.it.

Part of these papers, continued after the Brainstorming according to the discussions held in Sevilla, further polished and additionally refereed, are included in this volume; another series of papers were selected for a special issue of Soft Computing.

Very shortly stated, membrane computing is a branch of natural computing whose aim is to abstract a computing model from the structure and the functioning of the living cell. Basically, a membrane system (P system) is a distributedparallel computing model, where multisets of symbol-objects are processed in the compartments defined by a cell-like hierarchy of membranes.

These objects evolve by means of multiset rewriting-like rules and/or by communication rules (such as symport/antiport rules) which are applied in a maximally parallel (all objects which can evolve should do it) non-deterministic (the objects to process and the rules to apply are chosen in a random way) manner. There are many classes of P systems, with biological or mathematical motivation. For instance, the objects can be also strings of symbols, the membrane structure can be described by a graph (the so­called tissue P systems), or can itself evolve, e.g., by dissolution or by membrane division. Most of these types of systems were proven to be computationally universal, equivalent in power to Turing machines. In cases where an exponential space can be created in a polynomial time - for instance, by means of biologically well motivated operations, such as membrane division or membrane creation - by trading space for time one can solve computationally hard problems (typically, NP-complete problems) in polynomial (often, linear) time. In the last years, membrane computing also started to be used as a frame-work for modelling various biological phenomena, mainly at the cell level, as well as a toolkit for applications in linguistics, computer graphics, management, etc.

A comprehensive presentation of the domain, at the level of the spring of 2002, can be found in the monograph Gh. Paun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002, while the current bibliography of membrane computing (including many downloadable papers) can be found at the above mentioned web page.

The papers which follow illustrate all main research directions active in membrane computing: looking into biology for new ideas, followed then mathematically; comparing various types of P systems with Turing machines and their restrictions (in most cases, proving universality results); looking for better results from various points of view, such as the size of involved systems, their determinism, the ingredients they use for reaching the power of Turing machines; implementations on the usual computer (mainly for didactic purposes and for applications in modelling biological phenomena); ways to devise polynomial solutions to computationally hard problems, or solutions to various problems, more efficient than in sequential computing frameworks; tissue­like P systems, with the cells placed in the nodes of a graph; ways to add non­crisp mathematical features to P systems, such as probabilities, fuzzy sets or rough sets features.

What is missing is an illustration of another important trend in membrane computing, namely applications of a biological nature. A volume covering this topic (as well as other types of applications), also containing papers elaborated during the Brainstorming, is in preparation for Springer-Verlag.

As mentioned above, the meeting was organized by the Research Group on Natural Computing from Sevilla University (http://www.gcn.us.es) - and all the members of this group were involved in the work. Many participants have used funds from the CE MolCoNet Project IST-2001-32008. The Brainstorming also benefited from the support of the project TIC2002-04220-C03-01 of the Ministerio de Ciencia y Tecnología of Spain, of the Acción Coordinada IMUS 2003, of the Research Group PAI TIC 193 of the Junta de Andalucia, and of the Department of Computer Science and Artificial Intelligence from Sevilla University.

Sevilla, Spain
April, 2004